题目：传送门
题意：给你一个无向图，你需要找出里面的桥，并把所有桥按字典序输出
这一道题就是用无向图求桥的模板就可以了。
我一直错就是因为我在输入路径的时候少考虑一点
错误代码+原因：
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 #include<queue>
6 using namespace std;
7 const int maxn=1005;
8 struct shudui
9 {
10 int x,y;
11 bool operator < (const shudui t)const
12 {
13 if(x==t.x)
14 return y>t.y;
15 else return x>t.x;
16 }
17 }str1;
18 priority_queue<shudui>r;
19 int w[maxn][maxn];
20 int cnt,head[maxn],n,dfn[maxn],low[maxn],num,qua,root,iscut[maxn];
21 struct edge
22 {
23 int u,v,next;
24 }e[maxn*maxn];
25 void add_edge(int x,int y)
26 {
27 e[cnt].u=x;
28 e[cnt].v=y;
29 e[cnt].next=head[x];
30 head[x]=cnt++;
31 }
32 void tarjan(int x,int fx)
33 {
34 dfn[x]=low[x]=++num;
35 for(int i=head[x];i;i=e[i].next)
36 {
37 int to=e[i].v;
38 if(!dfn[to])
39 {
40 tarjan(to,i);
41 low[x]=min(low[x],low[to]);
42 if(low[to]>dfn[x])
43 { //因为我把双向边放在了一起，即1->2放在了cnt为2的地方，2->1放在了cnt为3的地方。
44 //那么就可以通过2^1=3找到另一个反方向的边，或者3^1=2.那么这个双向边就被标记成了桥
45 iscut[i]=iscut[i^1]=1;
46 }
47 }
48 else if(i!=(fx^1))
49 low[x]=min(dfn[to],low[x]);
50 }
51 }
52 int main()
53 {
54 while(~scanf("%d",&n))
55 {
56 if(n==0)
57 {
58 printf("0 critical links\n");
59 continue;
60 }
61 cnt=2;
62 num=qua=0;
63 memset(w,0,sizeof(w));
64 memset(iscut,0,sizeof(iscut));
65 memset(head,0,sizeof(head));
66 memset(dfn,0,sizeof(dfn));
67 memset(low,0,sizeof(low));
68 for(int i=1;i<=n;++i)
69 {
70 int x,y,sum;
71 char ch;
72 scanf("%d %c%d%c",&x,&ch,&sum,&ch);
73 x+=1;
74 while(sum--)
75 {
76 scanf("%d",&y);
77 y+=1;
78 if(!w[x][y]) //我原本是想要添加就添加一对互反方向的边(即1->2和2->1，因为用这种方式找桥的时
79 //候，你必须保证互反方向的边存在一起，这样可以通过i^1来找到边的另一个方向)。但是我有一点没有考虑到
80 //就是我这样判断的话如果题目给出两条1到2的无向边的时候我的代码就错了。因为我的代码默认
81 //只会给两点之间添加至多一次无向边
82 {
83 add_edge(x,y);
84 add_edge(y,x);
85 w[x][y]=w[y][x]=1;
86 }
87 }
88 }
89
90 for(int i=1;i<=n;++i)
91 {
92 if(!dfn[i])
93 {
94 tarjan(i,0);
95 }
96 }
97 int ans=0;
98 for(int i=2;i<cnt;i+=2)
99 {
100 if(iscut[i])
101 {
102 str1.x=min(e[i^1].v-1,e[i].v-1);
103 str1.y=max(e[i^1].v-1,e[i].v-1);
104 r.push(str1);
105 ans++;
106 }
107
108 }
109 printf("%d critical links\n",ans);
110 while(!r.empty())
111 {
112 str1=r.top();
113 r.pop();
114 printf("%d - %d\n",str1.x,str1.y);
115 }
116 printf("\n");
117 }
118 return 0;
119 }
正解代码1：
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 #include<queue>
6 #include<map>
7 #include<vector>
8 using namespace std;
9 const int maxn = 1e5+10;
10 const int M=1e5+10;
11 struct node {
12 int v, next;
13 }e[M];
14 struct shudui
15 {
16 int x,y;
17 bool operator < (const shudui t)const
18 {
19 if(x==t.x)
20 return y>t.y;
21 else return x>t.x;
22 }
23 }str1;
24 priority_queue<shudui>r;
25 map<int,int>w;
26 int head[maxn], cnt;
27 bool iscut[maxn];
28 int dfn[maxn], low[maxn];
29 int num,n;
30 inline void add_edge(int xx, int yy) {
31 e[++cnt].next = head[xx];
32 e[cnt].v = yy;
33 head[xx] = cnt;
34 }
35
36 inline void tarjan(int x, int in_edge) {
37 dfn[x] = low[x] = ++num;
38 for(int i = head[x]; i; i = e[i].next) {
39 int to = e[i].v;
40 if(!dfn[to]) {
41 tarjan(to, i);
42 low[x] = min(low[x], low[to]);
43 if(low[to] > dfn[x])
44 iscut[i] = iscut[i ^ 1] = true;
45 }
46 else if(i != (in_edge ^ 1))
47 low[x] = min(low[x], dfn[to]);
48 }
49 }
50 int main()
51 {
52 while(~scanf("%d",&n))
53 {
54 cnt=1;
55 num=0;
56 memset(iscut,0,sizeof(iscut));
57 memset(head,0,sizeof(head));
58 memset(dfn,0,sizeof(dfn));
59 memset(low,0,sizeof(low));
60 if(n==0)
61 {
62 printf("0 critical links\n\n");
63 continue;
64 }
65 int u,k,v;
66 for(int i = 1; i <= n; i++)
67 {
68 scanf("%d (%d)",&u,&k);
69 u++;
70 while(k--)
71 {
72 scanf("%d",&v);
73 v++;
74 if(v <= u)continue;
75 add_edge(u,v);
76 add_edge(v,u);
77 }
78 }
79 for(int i=1;i<=n;++i)
80 {
81 if(!dfn[i])
82 {
83 tarjan(i,0);
84 }
85 }
86 vector<pair<int,int> >ans;
87 int anss=0;
88 for(int i=2;i<cnt;i+=2)
89 {
90 if(iscut[i])
91 {
92 int xx=min(e[i^1].v-1,e[i].v-1);
93 int yy=max(e[i^1].v-1,e[i].v-1);
94 ans.push_back(make_pair(xx,yy));
95 anss++;
96 }
97
98 }
99 printf("%d critical links\n",anss);
100 sort(ans.begin(),ans.end()); //默认从小到大排序
101 for(int i = 0; i < ans.size(); i++)
102 printf("%d - %d\n",ans[i].first,ans[i].second);
103 printf("\n");
104 }
105 return 0;
106 }
正解代码2(kuangbin)：
1 #include <cstdio>
2 #include <iostream>
3 #include <cstring>
4 #include <algorithm>
5 #include <map>
6 #include <vector>
7 using namespace std;
8 const int N = 1e4+10;
9 const int M = 1e5+10;
10 struct Edge{
11 int to,next;
12 bool cut;//是否为桥的标记
13 }edge[M];
14 int head[N],tot,n;
15 int low[N],dfn[N],Stack[N];
16 int Index,top;
17 bool Instack[N],cut[N];
18 int add_block[N];//删除一个点后增加的连通块
19 int bridge;
20 void init(){
21 memset(head,-1,sizeof(head));
22 memset(dfn,0,sizeof(dfn));
23 memset(Instack,false,sizeof(Instack));
24 memset(add_block,0,sizeof(add_block));
25 memset(cut,false,sizeof(cut));
26 Index=top=bridge=tot = 0;
27 }
28 void addedge(int u,int v){
29 edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut = false;
30 head[u] = tot++;
31 }
32 void Tarjan(int u,int pre){
33 low[u] = dfn[u] = ++Index;
34 Stack[top++] = u;
35 Instack[u] = true;
36 int son = 0;
37 for(int i = head[u];i != -1;i = edge[i].next){
38 int v = edge[i].to;
39 if(v == pre)continue;
40 if( !dfn[v] ){
41 son++;
42 Tarjan(v,u);
43 if(low[u] > low[v])low[u] = low[v];
44 if(low[v] > dfn[u]){ //一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)<low(v)
45 bridge++;
46 edge[i].cut = true; //正反两边都标记为桥
47 edge[i^1].cut = true;
48 }
49 if(u != pre && low[v] >= dfn[u]){
50 cut[u] = true; //该点为割点
51 add_block[u]++;
52 }
53 }
54 else if( low[u] > dfn[v])low[u] = dfn[v];
55 }
56 if(u == pre && son > 1)cut[u] = true; //若u为根，且分支数>1，则u割点
57 if(u == pre)add_block[u] = son - 1;
58 Instack[u] = false;
59 top--;
60 }
61 void solve(){
62 for(int i = 1;i <= n;i++)
63 if( !dfn[i] )
64 Tarjan(i,i);
65 printf("%d critical links\n",bridge);
66
67 vector<pair<int,int> >ans; /*-- 将桥按顺序输出 --*/
68 for(int u = 1;u <= n;u++)
69 for(int i = head[u];i != -1;i = edge[i].next)
70 if(edge[i].cut && edge[i].to > u){
71 ans.push_back(make_pair(u,edge[i].to));
72 }
73 sort(ans.begin(),ans.end());
74 for(int i = 0;i < ans.size();i++)
75 printf("%d - %d\n",ans[i].first-1,ans[i].second-1);
76 printf("\n");
77 }
78 //处理重边
79 /*map<int,int>mapit;
80 inline bool isHash(int u,int v)
81 {
82 if(mapit[u*N+v])return true;
83 if(mapit[v*N+u])return true;
84 mapit[u*N+v] = mapit[v*N+u] = 1;
85 return false;
86 }*/
87 int main(){
88 while(scanf("%d",&n) == 1){
89 init();
90 int u,k,v;
91 //mapit.clear();
92 for(int i = 1;i <= n;i++){
93 scanf("%d (%d)",&u,&k);
94 u++;
95 //这样加边，要保证正边和反边是相邻的，建无向图
96 while(k--){
97 scanf("%d",&v);
98 v++;
99 if(v <= u)continue;
100 //if(isHash(u,v))continue;
101 addedge(u,v);
102 addedge(v,u);
103 }
104 }
105 solve();
106 }
107 return 0;
108 }
只求桥板子1：
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn = 100086;
4 struct node {
5 int y, net;
6 }e[maxn << 1];
7 int lin[maxn], len = 1;
8 bool bridge[maxn << 1];
9 int dfn[maxn], low[maxn];
10 int n, m, num;
11
12 inline int read() {
13 int x = 0, y = 1;
14 char ch = getchar();
15 while(!isdigit(ch)) {
16 if(ch == '-') y = -1;
17 ch = getchar();
18 }
19 while(isdigit(ch)) {
20 x = (x << 1) + (x << 3) + ch - '0';
21 ch = getchar();
22 }
23 return x * y;
24 }
25
26 inline void insert(int xx, int yy) {
27 e[++len].net = lin[xx];
28 e[len].y = yy;
29 lin[xx] = len;
30 }
31
32 inline void tarjan(int x, int in_edge) {
33 dfn[x] = low[x] = ++num;
34 for(int i = lin[x]; i; i = e[i].net) {
35 int to = e[i].y;
36 if(!dfn[to]) {
37 tarjan(to, i);
38 low[x] = min(low[x], low[to]);
39 if(low[to] > dfn[x])
40 bridge[i] = bridge[i ^ 1] = true;
41 }
42 else if(i != (in_edge ^ 1))
43 low[x] = min(low[x], dfn[to]);
44 }
45 }
46
47 int main() {
48 n = read(), m = read();
49 len = 1;
50 for(int i = 1; i <= m; ++i) {
51 int x, y, z;
52 x = read(), y = read();
53 insert(x, y);
54 insert(y, x);
55 }
56 for(int i = 1; i <= n; ++i)
57 if(!dfn[i]) tarjan(i, 0);
58 for(int i = 2; i < len; i += 2)
59 if(bridge[i])
60 cout << e[i ^ 1].y << ' ' << e[i].y << '\n';
61 return 0;
62 }
只求桥板子2：
1 #include <cstdio>
2 #include <iostream>
3 #include <cstring>
4 #include <algorithm>
5 #include <map>
6 #include <vector>
7 using namespace std;
8 const int N = 1e4+10;
9 const int M = 1e5+10;
10 struct Edge{
11 int to,next;
12 bool cut;//是否为桥的标记
13 }edge[M];
14 int head[N],tot,n;
15 int low[N],dfn[N],Stack[N];
16 int Index,top;
17 bool Instack[N],cut[N];
18 int add_block[N];//删除一个点后增加的连通块
19 int bridge;
20 void init(){
21 memset(head,-1,sizeof(head));
22 memset(dfn,0,sizeof(dfn));
23 memset(Instack,false,sizeof(Instack));
24 memset(add_block,0,sizeof(add_block));
25 memset(cut,false,sizeof(cut));
26 Index=top=bridge=tot = 0;
27 }
28 void addedge(int u,int v){
29 edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut = false;
30 head[u] = tot++;
31 }
32 void Tarjan(int u,int pre){
33 low[u] = dfn[u] = ++Index;
34 // Stack[top++] = u;
35 // Instack[u] = true;
36 int son = 0;
37 for(int i = head[u];i != -1;i = edge[i].next){
38 int v = edge[i].to;
39 if(v == pre)continue;
40 if( !dfn[v] ){
41 son++;
42 Tarjan(v,u);
43 if(low[u] > low[v])low[u] = low[v];
44 if(low[v] > dfn[u]){ //一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)<low(v)
45 bridge++;
46 edge[i].cut = true; //正反两边都标记为桥
47 edge[i^1].cut = true;
48 }
49 // if(u != pre && low[v] >= dfn[u]){
50 // cut[u] = true; //该点为割点
51 // add_block[u]++;
52 // }
53 }
54 else if( low[u] > dfn[v])low[u] = dfn[v];
55 }
56 // if(u == pre && son > 1)cut[u] = true; //若u为根，且分支数>1，则u割点
57 // if(u == pre)add_block[u] = son - 1;
58 // Instack[u] = false;
59 // top--;
60 }
61 void solve(){
62 for(int i = 1;i <= n;i++)
63 if( !dfn[i] )
64 Tarjan(i,i);
65 printf("%d critical links\n",bridge);
66
67 vector<pair<int,int> >ans; /*-- 将桥按顺序输出 --*/
68 for(int u = 1;u <= n;u++)
69 for(int i = head[u];i != -1;i = edge[i].next)
70 if(edge[i].cut && edge[i].to > u){
71 ans.push_back(make_pair(u,edge[i].to));
72 }
73 sort(ans.begin(),ans.end());
74 for(int i = 0;i < ans.size();i++)
75 printf("%d - %d\n",ans[i].first-1,ans[i].second-1);
76 printf("\n");
77 }
78 //处理重边
79 /*map<int,int>mapit;
80 inline bool isHash(int u,int v)
81 {
82 if(mapit[u*N+v])return true;
83 if(mapit[v*N+u])return true;
84 mapit[u*N+v] = mapit[v*N+u] = 1;
85 return false;
86 }*/
87 int main(){
88 while(scanf("%d",&n) == 1){
89 init();
90 int u,k,v;
91 //mapit.clear();
92 for(int i = 1;i <= n;i++){
93 scanf("%d (%d)",&u,&k);
94 u++;
95 //这样加边，要保证正边和反边是相邻的，建无向图
96 while(k--){
97 scanf("%d",&v);
98 v++;
99 if(v <= u)continue;
100 //if(isHash(u,v))continue;
101 addedge(u,v);
102 addedge(v,u);
103 }
104 }
105 solve();
106 }
107 return 0;
108 }