強聯(lián)通分量：是指點的一個子集以及這些點附帶的邊，這個子集中任意兩點能互相到達對方。
算法描述：
1. 用dfs遍歷有向圖，形成一個森林（注意是森林），遍歷時記下每個節(jié)點 i 所有子孫訪問完成的時刻。如 i 有子孫a,b,c，則dfs(a), dfs(b), dfs(c)后將時間戳賦給 finish[i]。
2. 將所有邊反向，構(gòu)成新的圖GT
3. 在GT上按點的時間戳降序做dfs，生成一個森林，每棵樹就是一個強聯(lián)通分量了。
強聯(lián)通分量的性質(zhì)：
1. 若 u,v 處于同一強聯(lián)通分量中，則所有邊反向后，它們?nèi)翁幵谕粡娐?lián)通分量中。
2. 在第二次 dfs 中，設(shè)點 u 的時間戳是當前所有未訪問的點中最大的，則 u 所在的強聯(lián)通分量 C 沒有邊指向其它未訪問的強聯(lián)通分量C'（注意是在G
T中）。因為若存在這樣的邊，則在G中存在邊從 C' 的點指向 C，則C‘中點時間戳肯定比 u 大（回想一下第一次 dfs 時我們是怎樣對點標時間戳的），與假設(shè)矛盾。
下面是代碼，最后是測試文件。輸出每個點屬于哪個強聯(lián)通分量。
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
const int maxn=100;
// 用于第一次dfs時記錄每個點的finish時間戳
struct finish{
int id;
int ftime;
}f[maxn];
// 這個結(jié)構(gòu)體用于第二次dfs時記錄每個點屬于哪個塊
struct component{
int cid;
int id;
}comp[maxn];
// 排序用
bool operator <(const finish &a, const finish &b)
{
return a.ftime<b.ftime;
}
// 鄰接表存儲
list<int> l[maxn];
list<int> lr[maxn];
// dfs訪問標識數(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記錄時間戳
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的時間戳來排序
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();
}
}
// 測試文件，包括兩個圖，第一個是聯(lián)通的，第二個不聯(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