強(qiáng)聯(lián)通分量：是指點(diǎn)的一個(gè)子集以及這些點(diǎn)附帶的邊，這個(gè)子集中任意兩點(diǎn)能互相到達(dá)對(duì)方。
算法描述：
1. 用dfs遍歷有向圖，形成一個(gè)森林（注意是森林），遍歷時(shí)記下每個(gè)節(jié)點(diǎn) i 所有子孫訪問(wèn)完成的時(shí)刻。如 i 有子孫a,b,c，則dfs(a), dfs(b), dfs(c)后將時(shí)間戳賦給 finish[i]。
2. 將所有邊反向，構(gòu)成新的圖GT
3. 在GT上按點(diǎn)的時(shí)間戳降序做dfs，生成一個(gè)森林，每棵樹就是一個(gè)強(qiáng)聯(lián)通分量了。
強(qiáng)聯(lián)通分量的性質(zhì)：
1. 若 u,v 處于同一強(qiáng)聯(lián)通分量中，則所有邊反向后，它們?nèi)翁幵谕粡?qiáng)聯(lián)通分量中。
2. 在第二次 dfs 中，設(shè)點(diǎn) u 的時(shí)間戳是當(dāng)前所有未訪問(wèn)的點(diǎn)中最大的，則 u 所在的強(qiáng)聯(lián)通分量 C 沒(méi)有邊指向其它未訪問(wèn)的強(qiáng)聯(lián)通分量C'（注意是在G
T中）。因?yàn)槿舸嬖谶@樣的邊，則在G中存在邊從 C' 的點(diǎn)指向 C，則C‘中點(diǎn)時(shí)間戳肯定比 u 大（回想一下第一次 dfs 時(shí)我們是怎樣對(duì)點(diǎn)標(biāo)時(shí)間戳的），與假設(shè)矛盾。
下面是代碼，最后是測(cè)試文件。輸出每個(gè)點(diǎn)屬于哪個(gè)強(qiáng)聯(lián)通分量。
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
const int maxn=100;
// 用于第一次dfs時(shí)記錄每個(gè)點(diǎn)的finish時(shí)間戳
struct finish{
int id;
int ftime;
}f[maxn];
// 這個(gè)結(jié)構(gòu)體用于第二次dfs時(shí)記錄每個(gè)點(diǎn)屬于哪個(gè)塊
struct component{
int cid;
int id;
}comp[maxn];
// 排序用
bool operator <(const finish &a, const finish &b)
{
return a.ftime<b.ftime;
}
// 鄰接表存儲(chǔ)
list<int> l[maxn];
list<int> lr[maxn];
// dfs訪問(wèn)標(biāo)識(shí)數(shù)組
int visit[maxn];
int t;
int n,e;
void dfs1(int k,int id)
{
visit[k]=id;
for(list<int>::iterator it=l[k].begin();it!=l[k].end();it++){
int x=(int)(*it);
if(visit[x]==-1) dfs1(x,id);
}
f[k].ftime=++t;
f[k].id=k;
}
void dfs2(int k,int cid)
{
visit[k]=cid;
comp[k].id=k;
comp[k].cid=cid;
for(list<int>::iterator it=lr[k].begin();it!=lr[k].end();it++){
int x=(int)(*it);
if(visit[x]==-1) dfs2(x,cid);
}
}
// 將圖的邊反向
void reverse()
{
for(int i=0;i<n;i++){
for(list<int>::iterator it=l[i].begin();it!=l[i].end();it++){
lr[(int)(*it)].push_back(i);
}
}
}
void clearList()
{
int i;
for(i=0;i<n;i++) l[i].clear(),lr[i].clear();
}
bool read()
{
int i,j,k;
if(scanf("%d%d",&n,&e)==EOF) return false;
for(i=0;i<e;i++){
scanf("%d%d",&j,&k);
l[j-1].push_back(k-1);
}
return true;
}
void solve()
{
int i,j,k;
memset(visit,-1,sizeof(visit));
// 第一次dfs記錄時(shí)間戳
int id=1;
t=0;
for(i=0;i<n;i++) if(visit[i]==-1){
dfs1(i,id++);
}
//for(i=0;i<n;i++) printf("%d ",visit[i]);
//printf("\n");
// 根據(jù)finish的時(shí)間戳來(lái)排序
sort(f,f+n);
// 所有邊反向
reverse();
for(i=n-1;i>=0;i--) printf("%d ",f[i].id);
printf("\n");
memset(visit,-1,sizeof(visit));
int cid=1;
for(i=n-1;i>=0;i--){
int x=f[i].id;
if(visit[x]==-1) dfs2(x,cid++);
}
for(i=0;i<n;i++) printf("%d ",comp[i].cid);
}
int main()
{
freopen("graph.txt","r",stdin);
while(read()){
solve();
clearList();
}
}
// 測(cè)試文件，包括兩個(gè)圖，第一個(gè)是聯(lián)通的，第二個(gè)不聯(lián)通
8 14
1 3
2 1
3 2
3 4
2 4
3 6
4 5
5 4
6 5
6 7
7 6
5 8
7 8
8 8
4 4
1 2
2 1
3 4
4 3