LightOJ 1026 Critical Links（割边模板题）

题目链接：点击这里

题意：按字典序输出所有割边。

注意本题的输入，无向图的无向边不是对称存储的，用邻接表存储无向边有些不方便。

为了能存储边上的更多信息，采用链式前向星存储。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
typedef pair<int,int> PII;
const int N = 100010, M = N * 2;

struct edge
{
    int from, to, ne;
    bool cut;						// 记录该边是否为桥
    edge() { }
    edge(int a, int b, int c, bool d) : from(a), to(b), ne(c), cut(d) { }
}e[M];

int h[N], tot;
int dfn[N], low[N], timestamp;
vector<PII> ans;

void add(int a, int b)				// 添边
{
	e[tot] = edge(a, b, h[a], false);
	h[a] = tot++;
}

void tarjan(int x, int father)
{
	low[x] = dfn[x] = ++timestamp;
    for(int i = h[x]; i != -1; i = e[i].ne)
	{
        int y = e[i].to;
		if(!dfn[y])
		{
            tarjan(y, x);
            
			low[x] = min(low[x], low[y]);
            
			if(dfn[x] < low[y])
				e[i].cut = true;
        }
        else if(y != father)
            low[x] = min(low[x], dfn[y]);
    }
}

int main()
{
	int T;
    scanf("%d", &T);
    
    for(int j = 1; j <= T; j++)
    {
        memset(low, 0, sizeof low);
        memset(dfn, 0, sizeof dfn);
        memset(h, -1, sizeof h);
        tot = timestamp = 0;
        ans.clear();
        
        int n;
		scanf("%d", &n);
        for(int i = 0; i < n; i++)
		{
            int a, b, c;
            scanf("%d (%d)", &a, &b);
            while(b--)
			{
                scanf("%d", &c);
            	add(a, c);
            }
        }
        
        for(int i = 0; i < n; i++)
            if(!dfn[i])
                tarjan(i, -1);
                
        for(int i = 0; i < tot; i++)
        {
        	if(e[i].cut)
        	{
        		int x = e[i].from, y = e[i].to;
        		ans.push_back(make_pair(min(x, y), max(x, y)));
			}
		}
		
		sort(ans.begin(), ans.end());
        
        printf("Case %d:\n", j);
        int cnt = ans.size();
        printf("%d critical links\n", cnt);
        for(int i = 0; i < cnt; i++)
            printf("%d - %d\n", ans[i].first, ans[i].second);
    }
    
	return 0;
}