有向图强连通分量.cpp

本人参加ACM竞赛使用的一些算法模板

/***********************************************************
*   有向图强连通分量Tarjan算法
*   扩展：求出强连通后把强连通缩点是一个DAG，对DAG求传递闭包
*   复杂度是O(E)的，可借此求有向图的连通性。
*   (poj 2553	The Bottom of a Graph )
***********************************************************/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;

const int MAXN = 5001;
int V, E;//点数、边数
int pt, ptR;
struct node
{
    int v, next;//当前节点，下一节点位置
};
node adjlst[MAXN * 1000];//邻接表

bool sink[MAXN];
int prev[MAXN], low[MAXN], stk[MAXN], sc[MAXN];
int cnt[MAXN];
int cnt0, ptr, cnt1;
void dfs(int w)
{
	int Min(0);
	prev[w] = cnt0++;
	low[w] = prev[w];
	Min = low[w];
	stk[ptr++] = w;
	for(int i = adjlst[w].next; i != -1; i = adjlst[i].next)
	{
		int t = adjlst[i].v;
		if(prev[t] == -1)
			dfs(t);
		if(low[t] < Min)
			Min = low[t];
	}
	if(Min < low[w])
	{
		low[w] = Min;
		return;
	}
	do
	{
		int v = stk[--ptr];
		sc[v] = cnt1;
		low[v] = MAXN;
	}while(stk[ptr] != w);
	++cnt1;
}
void Tarjan(int N)
{//传入N为点数，结果保存在sc数组中，同一标号的点在同一个强连通分量内，
//强连通分量数为cnt1
	cnt0 = cnt1 = ptr = 0;
	int i;
	for(i = 0; i < N; ++i)
		prev[i] = low[i] = -1;
	for(i = 0; i < N; ++i)
		if(prev[i] == -1)
			dfs(i);
};
int last[MAXN];
int main()
{
	int i, j;
    for(; ;)
    {
        scanf("%d", &V);
        if(!V) break;
        scanf("%d", &E);
        for(i = 0; i < V; i++)
        {
            adjlst[i].next = -1;
            last[i] = i;
		}
        pt = V;
        ptR = V;
        for(i = 0; i < E; i++)
        {
            int a, b;
            scanf("%d %d", &a, &b);
            if(a == b) continue;
            int pa = --a, pb = --b;
            //while(adjlst[pa].next != -1)
            pa = last[a]; //adjlst[pa].next;
            adjlst[pa].next = pt;
            adjlst[pt].v = b;
            last[a] = pt;
            adjlst[pt++].next = -1;
        }
        Tarjan(V);
        set<int> kn;
        for(i = 0; i < V; i++)
        {
            for(int t = adjlst[i].next; t != -1; t = adjlst[t].next)
                if(sc[i] != sc[adjlst[t].v])
                {
                    kn.insert(sc[i]);
                    break;
                }
        }
        for(i = 0; i < V; ++i)
        	sink[i] = false;
        for(i = 0; i < V; i++)
            if(kn.find(sc[i]) == kn.end() ) sink[i] = true;
        bool flag(false);
        for(i = 0; i < V; i++)
        {
            if(sink[i])
            {
                if(flag) printf(" ");
                flag = true;
                printf("%d", i + 1);
            }
        }
        printf("\n");
    }
    return 0;
}