强连通分量 ( Tarjan，邻接链表 )——The Bottom of a Graph ( POJ 2553 )

• 题目链接：
  http://poj.org/problem?id=2553

• 分析：
  给出一有向图，求除所以出度为0的强连通分量，然后按顺序输出其中的节点。

• 题解：
  先用 tarjan 求出所有的强连通分量，然后遍历所有点，如果某个点指向一个不在其强连通分量中的点，这个强连通分量的出度++，最后统计所有出度为0的强连通分量，然后输出其中的点。

• 代码：

1.建图：

#define MAXM 50010
#define MAXV 10010
struct Edge
{
int s,t,next;
} edge[MAXM];
int headlist[MAXV];
void Add(int a, int b, int i)
{
    edge[i].s=a;
    edge[i].t=b;
    edge[i].next=headlist[a];
    headlist[a]=i;
}

2.tarjan求强连通分量：

int dfn[MAXV];                                  //第一次访问的步数
int low[MAXV];                                  //子树中最早的步数
int stap[MAXV],stop;                            //模拟栈
bool instack[MAXV];                         //是否在栈中
int Count;                                      //记录连通分量的个数
int cnt;                                            //记录搜索步数
int belong[MAXV];                               //属于哪个连通分量

void tarjan(int x)
{
int i;
    dfn[x]=low[x]=++cnt;
    stap[stop++]=x;
    instack[x]=true;
for(i=headlist[x];i!=-1;i=edge[i].next)
    {
int a=edge[i].t;
if(!dfn[a]){
            tarjan(a);
            low[x]=min(low[a],low[x]);
        }else if(instack[a])
            low[x]=min(dfn[a],low[x]);
    }

if(low[x]==dfn[x])
    {
        Count++;
while(1)
        {
int tmp=stap[--stop];
            belong[tmp]=Count;
            instack[tmp]=false;
if(tmp==x) break;
        }
    }
}

3.找出出度为0的强连通分量：

void output()
{
int i,j,outdegree[MAXV]={0};
for(i=1;i<=n;i++)
for(j=headlist[i];j!=-1;j=edge[j].next)
if(belong[i]!=belong[edge[j].t])
                outdegree[belong[i]]++;

memset(instack,0,sizeof(instack));
for(i=1;i<=n;i++)
if(!outdegree[belong[i]]) instack[i]=1;

for(i=1;i<=n;i++)
if(instack[i]) printf("%d ",i);
printf("\n");
}

• 参考代码：

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <stack>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef pair<int,int> Pii;
typedef long long LL;
typedef unsigned long long ULL;
typedef double DBL;
typedef long double LDBL;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define Sqr(a) ((a)*(a))

#define MAXM 50010
#define MAXV 10010
#define min(a,b) (a>b?b:a)
struct Edge
{
int s,t,next;
} edge[MAXM];
int n,m,headlist[MAXV];

int dfn[MAXV];                                  //第一次访问的步数
int low[MAXV];                                  //子树中最早的步数
int stap[MAXV],stop;                            //模拟栈
bool instack[MAXV];                         //是否在栈中
int Count;                                      //记录连通分量的个数
int cnt;                                            //记录搜索步数
int belong[MAXV];                               //属于哪个连通分量

void init()
{
    Count=stop=cnt=0;
memset(instack,false,sizeof(instack));
memset(dfn,0,sizeof(dfn));
}

void Add(int a, int b, int i)
{
    edge[i].s=a;
    edge[i].t=b;
    edge[i].next=headlist[a];
    headlist[a]=i;
}

void tarjan(int x)
{
int i;
    dfn[x]=low[x]=++cnt;
    stap[stop++]=x;
    instack[x]=true;
for(i=headlist[x];i!=-1;i=edge[i].next)
    {
int a=edge[i].t;
if(!dfn[a]){
            tarjan(a);
            low[x]=min(low[a],low[x]);
        }else if(instack[a])
            low[x]=min(dfn[a],low[x]);
    }

if(low[x]==dfn[x])
    {
        Count++;
while(1)
        {
int tmp=stap[--stop];
            belong[tmp]=Count;
            instack[tmp]=false;
if(tmp==x) break;
        }
    }
}

void work()
{
    init();
for(int i=1;i<=n;i++)
if(!dfn[i])
            tarjan(i);
}

void output()
{
int i,j,outdegree[MAXV]={0};
for(i=1;i<=n;i++)
for(j=headlist[i];j!=-1;j=edge[j].next)
if(belong[i]!=belong[edge[j].t])
                outdegree[belong[i]]++;

memset(instack,0,sizeof(instack));
for(i=1;i<=n;i++)
if(!outdegree[belong[i]]) instack[i]=1;

for(i=1;i<=n;i++)
if(instack[i]) printf("%d ",i);
printf("\n");
}

int main()
{
int i,a,b;
while(~scanf("%d%d",&n,&m))
    {
memset(headlist,-1,sizeof(headlist));
for(i=0;i<m;i++)
        {
scanf("%d%d",&a,&b);
            Add(a, b, i);
        }
        work();
        output();
    }
return 0;
}