https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=737
题目大意：给你一个网络要求这里面的桥。
输入数据：
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> #define N 12010 using namespace std; struct st { int x, y; bool friend operator < (st a, st b) { if(a.x == b.x) return a.y < b.y; return a.x < b.x; }//结构体优先级 } node[N]; vector<vector<int> >G; int low[N], dfn[N], f[N]; int n, Time, k; void Init() { G.clear(); G.resize(n + 1); memset(low, 0, sizeof(low)); memset(dfn, 0, sizeof(dfn)); memset(f, 0, sizeof(f)); Time = k = 0; } void Tarjan(int u, int fa) { int i, len, v; low[u] = dfn[u] = ++Time; f[u] = fa; len = G[u].size(); for(i = 0 ; i < len ; i++) { v = G[u][i]; if(!dfn[v]) { Tarjan(v, u); low[u] = min(low[u], low[v]); } else if(fa != v) low[u] = min(low[u], dfn[v]); } } void Solve() { int i, v; for(i = 0 ; i < n ; i++) if(!low[i]) Tarjan(i, -1); for(i = 0 ; i < n ; i++) { v = f[i]; if(v > -1 && dfn[v] < low[i]) { node[k].x = v; node[k].y = i; if(node[k].x > node[k].y) swap(node[k].x, node[k].y); k++; } } sort(node, node + k);//sort排序 printf("%d critical links ", k); for(i = 0 ; i < k ; i++) printf("%d - %d ", node[i].x, node[i].y); printf(" "); } int main() { int a, b, m, x; while(~scanf("%d", &n)) { Init(); x = n; while(x--) { scanf("%d (%d)", &a, &m); while(m--) { scanf("%d", &b); G[a].push_back(b); } } Solve(); } return 0; }