题目大意：给你一个网络要求这里面的桥。
输入数据：
n 个点
点的编号 （与这个点相连的点的个数m） 依次是m个点的
输入到文件结束。
桥输出的时候需要排序
知识汇总：
桥： 无向连通图中，如果删除某条边后，图变成不连通了，则该边为桥。
求桥：
在求割点的基础上吗，假如一个边没有重边（重边 1-2, 1->2 有两次，那么 1->2 就是有两条边了，那么 1->2就不算是桥了）。
当且仅当 (u,v) 为父子边，且满足 dfn[u] < low[v]
这里对重边处理的时候用了两种方法。写了两个代码，也挺简单的。
#include <iostream> #include <cstdlib> #include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <cmath> #include <stack> #include <cstring> using namespace std; #define INF 0xfffffff #define maxn 11005 #define min(a,b) (a<b?a:b) struct node { int x, y; bool friend operator < (node A,node B) { if(A.x == B.x) return A.y < B.y; return A.x < B.x; } }bridge[maxn]; int n, dfn[maxn], low[maxn], Father[maxn], Time; vector<int> G[maxn]; void init() { memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(Father, 0, sizeof(Father)); Time = 0; for(int i=0; i<n; i++) G[i].clear(); } void Tarjan(int u,int fa) { Father[u] = fa; low[u] = dfn[u] = ++Time; int len = G[u].size(), v, k = 0; for(int i=0; i<len; i++) { v = G[u][i]; if(v == fa && !k) { k ++; continue; } if( !low[v] ) { Tarjan(v, u); low[u] = min(low[u], low[v]); } else low[u] = min(low[u], dfn[v]); } } void solve() { int ans = 0; for(int i=0; i<n; i++) { if(!dfn[i]) Tarjan(i,-1); } for(int i=0; i<n; i++) { int v = Father[i]; if(dfn[v] < low[i] && v != -1) { bridge[ans].x = i; bridge[ans].y = v; if(bridge[ans].x > bridge[ans].y) swap(bridge[ans].x, bridge[ans].y); ans ++; } } sort(bridge, bridge + ans); printf("%d critical links ", ans); for(int i=0; i<ans; i++) { printf("%d - %d ",bridge[i].x,bridge[i].y); } printf(" "); } int main() { while(scanf("%d",&n) != EOF) { init(); for(int i=0; i<n; i++) { int a, b, m; scanf("%d (%d)",&a,&m); while(m--) { scanf("%d", &b); G[a].push_back(b); // G[b].push_back(a); } } solve(); } return 0; } /** 8 0 (1) 1 1 (3) 2 0 3 2 (2) 1 3 3 (3) 1 2 4 4 (1) 3 7 (1) 6 6 (1) 7 5 (0) */ #include <iostream> #include <cstdlib> #include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <cmath> #include <stack> #include <cstring> usingnamespace std; #define INF 0xfffffff #define maxn 11005 #define min(a,b) (a<b?a:b) /** 无向图求桥 **/struct node { int x, y; bool friend operator < (node A,node B) { if(A.x == B.x) return A.y < B.y; return A.x < B.x; } }bridge[maxn]; int n, dfn[maxn], low[maxn], Father[maxn], Time; vector<int> G[maxn]; void init() { memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(Father, 0, sizeof(Father)); Time = 0; for(int i=0; i<n; i++) G[i].clear(); } void Tarjan(int u,int fa) { Father[u] = fa; low[u] = dfn[u] = ++Time; int len = G[u].size(), v; for(int i=0; i<len; i++) { v = G[u][i]; if( !low[v] ) { Tarjan(v, u); low[u] = min(low[u], low[v]); } elseif(fa != v) low[u] = min(low[u], dfn[v]); } } void solve() { int ans = 0; for(int i=0; i<n; i++) { if(!low[i]) Tarjan(i, -1); } for(int i=0; i<n; i++) { int v = Father[i]; if(v != -1 && dfn[v] < low[i]) { bridge[ans].x = i; bridge[ans].y = v; if(bridge[ans].x > bridge[ans].y) swap(bridge[ans].x, bridge[ans].y); ans ++; } } sort(bridge, bridge + ans); printf("%d critical links ", ans); for(int i=0; i<ans; i++) { printf("%d - %d ",bridge[i].x,bridge[i].y); } printf(" "); } int main() { while(scanf("%d",&n) != EOF) { init(); for(int i=0; i<n; i++) { int a, b, m; scanf("%d (%d)",&a,&m); while(m--) { scanf("%d", &b); G[a].push_back(b); G[b].push_back(a); } } solve(); } return0; }