题目大意：给你一个网络要求这里面的桥。
输入数据：
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, , sizeof(dfn));
memset(low, , sizeof(low));
memset(Father, , sizeof(Father));
Time = ;
for(int i=; 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 = ; for(int i=; 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 = ;
for(int i=; i<n; i++)
{
if(!dfn[i])
Tarjan(i,-);
} for(int i=; i<n; i++)
{
int v = Father[i];
if(dfn[v] < low[i] && v != -)
{ 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\n", ans); for(int i=; i<ans; i++)
{
printf("%d - %d\n",bridge[i].x,bridge[i].y);
}
printf("\n");
} int main()
{
while(scanf("%d",&n) != EOF)
{
init();
for(int i=; 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 ;
} /**
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, , sizeof(dfn));
memset(low, , sizeof(low));
memset(Father, , sizeof(Father));
Time = ;
for(int i=; 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=; 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 = ;
for(int i=; i<n; i++)
{
if(!low[i])
Tarjan(i, -);
} for(int i=; i<n; i++)
{
int v = Father[i];
if(v != - && 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\n", ans); for(int i=; i<ans; i++)
{
printf("%d - %d\n",bridge[i].x,bridge[i].y);
}
printf("\n");
} int main()
{
while(scanf("%d",&n) != EOF)
{
init();
for(int i=; 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;
}