无向图求桥 UVA 796

***桥的概念：无向连通图中，如果删除某边后，图变 成不连通，则称该边为桥。***

***一条边(u,v)是桥，当且仅当(u,v)为树枝边，且 满足dfn(u)<low(v)（前提是其没有重边），非树枝边不可 能是桥

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=122091#problem/C***

***在这里还用了vector来保存一个图，这样会省去很大的空间***

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define N 100005

int n, m;
int dfn[N], low[N], Father[N];
int Time;

vector<vector<int> > G;

struct node
{
    int x, y;
}bridge[N];

int cmp(node a, node b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}

void Init()
{
    G.clear();
    G.resize(n+5);
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(Father, 0, sizeof(Father));
    Time=0;
}

void Tarjan(int u, int fa)
{
    dfn[u]=low[u]=++Time;
    Father[u]=fa;
    int len=G[u].size(), v;

    for(int 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()
{
    for(int i=0; i<n; i++)
    {
        if(!low[i])
            Tarjan(i, -1);
    }

    int ans=0, v;

    for(int i=0; i<n; i++)
    {
        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, cmp);

    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))
    {
        Init();
        for(int i=1; i<=n; i++)
        {
            int a, b;
            scanf("%d (%d)", &a, &m);
            while(m--)
            {
                scanf("%d", &b);
                G[a].push_back(b);
                G[b].push_back(a);
            }
        }
        solve();
    }
    return 0;
}