题干：
There are some locations in a park, and some of them are connected by roads. The park manger needs to build some railways along the roads, and he would like to arrange tourist routes to each circuit. If a railway belongs to more than one tourist routes, there might be clash on it, and if a railway belongs to none tourist route, it doesn’t need to build.
Now we know the plan, and can you tell us how many railways are no need to build and how many railways where clash might happen.
Input
The Input consists of multiple test cases. The first line of each test case contains two integers, n (0 < n <= 10000), m (0 <= m <= 100000), which are the number of locations and the number of the railways. The next m lines, each line contains two integers, u, v (0 <= u, v < n), which means the manger plans to build a railway on the road between u and v.
You can assume that there is no loop and no multiple edges.
The last test case is followed by two zeros on a single line, which means the end of the input.
Output
Output the number of railways that are no need to build, and the number of railways where clash might happen. Please follow the format as the sample.
Sample Input
8 10
0 1
1 2
2 3
3 0
3 4
4 5
5 6
6 7
7 4
5 7
0 0 Sample Output
1 5 题目大意：
有一个公园有n个景点，公园的管理员准备修建m条道路，并且安排一些形成回路的参观路线。如果一条道路被多条道路公用，那么这条路是冲突的；如果一条道路没在任何一个回路内，那么这条路是多余的 问分别有多少条有冲突的路和多余的路
解题报告：
首先我们可以知道多余边就是该无向图中的桥,桥必然不在任何环中。
冲突边只能在点双连通分量中,而什么样的点双连通分量有冲突边呢?
下面怎么判断呢？思路过程是这样的：（这个思想很精彩呀）
先手动找一个临界点（凭感觉）对于有n个节点和n条边(或小于n条边，比如2点1边)的点双连通分量，这种分量只有一个大环，不存在其他任何环了，所以这种分量中的边都不是冲突边。
对于有n个节点和m条边(m>n)的点双连通分量来说，有了刚刚的邻接点，这个就很好判断了。该分量内的所有边都是冲突边.因为边数>点数,所以该分量必有至少两个环,我们随便画个图就可知其中的任意边都至少在两个以上的环上.
综上所述,对于多余边,我们输出桥数.对于冲突边,我们输出边数>点数的点双连通分量的所有边数.
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
vector<int> vv[MAX];
int n,m;
int dfn[MAX],low[MAX],col[MAX];
int index,clk,bcc;
int ans1,ans2,num[MAX];
struct Edge {
int u,v;
Edge(int u=0,int v=0):u(u),v(v){}
} stk[MAX];
void init() {
for(int i = 0; i<=n; i++) {
vv[i].clear();
dfn[i]=low[i]=col[i]=0;
}
clk = index = bcc = 0;
ans1=ans2=0;
}
bool vis[MAX];
void cal(int tot) {//当前点双连通分量共有tot个点（当然，其中可能有重叠点） (不对，应该是没有重复点？不然后面不能直接sum > tot 来判断啊？)
int sum = 0;//当前点双连通分量共有sum条边
memset(vis,0,sizeof vis);
for(int i = 1; i<=tot; i++) vis[num[i]] = 1;
for(int i = 1; i<=tot; i++) {
int u = num[i];
int up = vv[u].size();
for(int j = 0; j<up; j++) {
if(vis[vv[u][j]]) sum++;
}
}
sum /= 2;//因为是无向图所以要除以2
if(sum > tot) ans2 += sum;
}
void tarjan(int x,int rt) {
dfn[x] = low[x] = ++clk;
int up = vv[x].size();
for(int i = 0; i<up; i++) {
int v = vv[x][i];
if(v == rt) continue;//这题说了无自环无重边，所以可以直接这样判断
if(dfn[v] == 0) {
stk[++index] = Edge(x,v);
tarjan(v,x);
low[x] = min(low[x],low[v]);
if(low[v] >= dfn[x]) {
bcc++;
int cnt = 0;
while(1) {
Edge tmp = stk[index];index--;
if(col[tmp.u] != bcc) {
num[++cnt] = tmp.u;col[tmp.u] = bcc;
}
if(col[tmp.v] != bcc) {
num[++cnt] = tmp.v;col[tmp.v] = bcc;
}
if(tmp.u == x && tmp.v == v) break;
}
cal(cnt);
}
}
else if(dfn[v] < dfn[x]) {//这里必须是两个dfn！ 也不能直接写else
stk[++index] = Edge(x,v);
low[x] = min(low[x],dfn[v]);
}
if(low[v] > dfn[x]) ans1++; //这句放到dfn[v]==0那里也可以 ，放到这里应该也没错！
}
}
int main()
{
while(~scanf("%d%d",&n,&m)) {
if(n == 0 && m == 0) break;
init();
for(int u,v,i = 1; i<=m; i++) {
scanf("%d%d",&u,&v);
vv[u].pb(v);vv[v].pb(u);
}
for(int i = 0; i<n; i++) {
if(dfn[i] == 0) tarjan(i,-1);//因为题目保证是连通图所以其实可以直接tarjan(1,-1)的
}
printf("%d %d\n",ans1,ans2);
}
return 0 ;
} 有几点要注意：
1.cal函数中的这个tot（也就是tarjan函数中的cnt），是可以直接代表当前点双连通分量中的点数的，不会有重复，因为你在if(col[tmp.u] != bcc)中都判掉了，这里非常巧妙！不能写成if(col[tmp.u] == 0) 则染色。而应该写成if(col[tmp.u]!=bcc) 则染成当前bcc。原因也很简单，就是一个点可能属于多个bcc！！！但是同一时间只可能会操作同一个bcc（也就是同一层的函数中，只可能会判断出一个bcc来，也就是说bcc这个变量不会发生变化），所以要染色成当前操作的bcc的时候，直接判断是否等于当前bcc就好了。这个写法非常精彩！
2.那里不能直接写else，因为这个情况：（假设是直接else了）
首先很显然5，1是割点，6->5->1->2->3->4了之后把这六条边全都压栈，然后回溯到1的时候发现1是割点，记录一下，并且③④⑤⑥全部出栈，然后再走1-4这条边，就直接进入else压栈了（也就是这一步错了，因为本身不该压栈的）。然后回溯回5，发现5是割点(因为low[1]>=dfn[5]成立，说明5是割点！不要认为说明1是割点！你要知道你遍历的时候是5是父节点1是子节点！)，然后记录一下，②⑥出栈（这时候⑥又被计算了一次。要知道虽然是点双，所以每个顶点可能被计算多次，但是每条边依旧是只能被计算一次！所以被计算两次就是个错误，更何况5号点和⑥号边，半毛钱关系都没有，隔着老远咧。）
3.同样是这个地方，也不能像一般的求割点那样，写成else if(dfn[v] < low[x])！！！因为这种情况：
你如果这样写，那⑥⑦这个边就没法处理了
其实仔细思考，为什么要在这里加上一步边入栈，其实就是想把所有的边都考虑进去。但是进一步想，加边进去最终的目的，还是要选出所有的点出来，而加最后一步边的两个点，肯定都属于之前的两条边了，所以最后这一条边加不加都可以。综上，我又尝试了一下直接去掉这一步加边，后来发现也AC了。代码如下：
AC代码2：（复习的时候看这个就行）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
vector<int> vv[MAX];
int n,m;
int dfn[MAX],low[MAX],col[MAX];
int index,clk,bcc;
int ans1,ans2,num[MAX];
struct Edge {
int u,v;
Edge(int u=0,int v=0):u(u),v(v){}
} stk[MAX];
void init() {
for(int i = 0; i<=n; i++) {
vv[i].clear();
dfn[i]=low[i]=col[i]=0;
}
clk = index = bcc = 0;
ans1=ans2=0;
}
bool vis[MAX];
void cal(int tot) {//当前点双连通分量共有tot个点（当然，其中可能有重叠点） (不对，应该是没有重复点？不然后面不能直接sum > tot 来判断啊？)
int sum = 0;//当前点双连通分量共有sum条边
memset(vis,0,sizeof vis);
for(int i = 1; i<=tot; i++) vis[num[i]] = 1;
for(int i = 1; i<=tot; i++) {
int u = num[i];
int up = vv[u].size();
for(int j = 0; j<up; j++) {
if(vis[vv[u][j]]) sum++;
}
}
sum /= 2;//因为是无向图所以要除以2
if(sum > tot) ans2 += sum;
}
void tarjan(int x,int rt) {
dfn[x] = low[x] = ++clk;
int up = vv[x].size();
for(int i = 0; i<up; i++) {
int v = vv[x][i];
if(v == rt) continue;//这题说了无自环无重边，所以可以直接这样判断
if(dfn[v] == 0) {
stk[++index] = Edge(x,v);
tarjan(v,x);
low[x] = min(low[x],low[v]);
if(low[v] >= dfn[x]) {
bcc++;
int cnt = 0;
while(1) {
Edge tmp = stk[index];index--;
if(col[tmp.u] != bcc) {
num[++cnt] = tmp.u;col[tmp.u] = bcc;
}
if(col[tmp.v] != bcc) {
num[++cnt] = tmp.v;col[tmp.v] = bcc;
}
if(tmp.u == x && tmp.v == v) break;
}
cal(cnt);
}
}
else low[x] = min(low[x],dfn[v]);
if(low[v] > dfn[x]) ans1++; //这句放到dfn[v]==0那里也可以 ，放到这里应该也没错！
}
}
int main()
{
while(~scanf("%d%d",&n,&m)) {
if(n == 0 && m == 0) break;
init();
for(int u,v,i = 1; i<=m; i++) {
scanf("%d%d",&u,&v);
vv[u].pb(v);vv[v].pb(u);
}
for(int i = 0; i<n; i++) {
if(dfn[i] == 0) tarjan(i,-1);//因为题目保证是连通图所以其实可以直接tarjan(1,-1)的
}
printf("%d %d\n",ans1,ans2);
}
return 0 ;
} AC代码3：（网上找的一个用set代替cal函数的版本）传送门
#include <bits/stdc++.h>
using namespace std;
const int M = 200010;
const int N = 10010;
struct Edge {
int from, to;
int next;
} edge[M];
int head[N];
int cnt_edge;
void add_edge(int u, int v)
{
edge[cnt_edge].from = u;
edge[cnt_edge].to = v;
edge[cnt_edge].next = head[u];
head[u] = cnt_edge++;
}
int dfn[N]; int idx;
int low[N];
stack<Edge> stk;
set<int> bcc;
int cut; // 桥的数量
int ans; // 冲突边数量
int m, n;
void dfs(int u, int pre)
{
dfn[u] = low[u] = ++idx;
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (v == pre) continue;
if (!dfn[v])
{
stk.push(edge[i]);
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) // 割点
{
Edge tmp;
int cnt = 0;
bcc.clear();
do {
cnt++;
tmp = stk.top();
stk.pop();
bcc.insert(tmp.from);
bcc.insert(tmp.to);
} while (tmp.from != u || tmp.to != v);
if (cnt > bcc.size()) ans += cnt;
}
if (low[v] > dfn[u]) ++cut;
}
else if (dfn[v] < dfn[u])
{
stk.push(edge[i]);
low[u] = min(low[u], dfn[v]);
}
}
}
void init()
{
memset(head, -1, sizeof head);
memset(dfn, 0, sizeof dfn);
ans = cut = cnt_edge = idx = 0;
}
int main()
{
while (~scanf("%d%d", &n, &m))
{
if (n == 0 && m == 0) break;
int u, v;
init();
for (int i = 0; i < m; ++i)
{
scanf("%d%d", &u, &v);
add_edge(u, v);
add_edge(v, u);
}
for (int i = 1; i <= n; ++i)
if (!dfn[i]) dfs(i, -1);
printf("%d %d\n", cut, ans);
}
return 0;
}
京公网安备 11010502036488号