题目链接：
题目描述：
题目中给出一个有可能不连通的无向图，求出这个图的桥，并且把桥按照起点升序输出（还有啊，还有啊，每个桥的起点要比终点靠前啊），这个题目读了好几遍，但是依旧没有找到数据范围写在哪里，经过无数次runtime error最终把范围定在1W左右。（题目晦涩难懂，wa到死了，嗷~~~~~~）
解题思路：
就是用Tarjan算法dfs出low和dfn数组，然后记录下来起点和终点排好序的桥，然后把桥排序输出就ok了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int maxn = ;
struct node
{
int to, next;
} edge[maxn*];
bool cmp (node a, node b)
{
if (a.next == b.next)
return a.to < b.to;
return a.next < b.next;
}
int low[maxn], dfn[maxn], head[maxn];
int Father[maxn], tot, ntime, cnt;
node Q[maxn * ];
void init ()
{
ntime = tot = cnt = ;
memset (low, , sizeof(low));
memset (dfn, , sizeof(dfn));
memset (head, -, sizeof(head));
memset (Father, , sizeof(Father));
}
void Add (int from, int to)
{
edge[tot].to = to;
edge[tot].next = head[from];
head[from] = tot ++;
}
void Tarjan (int u, int father)
{
low[u] = dfn[u] = ++ntime;
Father[u] = father;
for (int i=head[u]; i!=-; i=edge[i].next)
{
int v = edge[i].to;
if (!dfn[v])
{
Tarjan (v, u);
low[u] = min (low[u], low[v]);
}
else if (father != v)
low[u] = min (low[u], dfn[v]);
}
}
int main ()
{
int n, m;
node q;
while (scanf ("%d", &n) != EOF)
{
init ();
m = n;
while (n --)
{
int u , k;
scanf ("%d (%d)", &u, &k);
while (k --)
{
int v;
scanf ("%d", &v);
Add (u, v);
Add (v, u);
}
}
for (int i=; i<m; i++)
if (!dfn[i])
Tarjan (i, -); for (int i=; i<m; i++)
{
int v = Father[i];
if (v != - && dfn[v] < low[i])
{
q.next = v;
q.to = i;
if (q.next > q.to)
swap(q.next, q.to);
Q[cnt++] = q;
}
}
printf ("%d critical links\n", cnt);
sort (Q, Q+cnt, cmp);
for (int i=; i<cnt; i++)
printf ("%d - %d\n", Q[i].next, Q[i].to);
printf ("\n");
}
return ;
}