强联通分量：是指点的一个子集以及这些点附带的边，这个子集中任意两点能互相到达对方。
算法描述：
1. 用dfs遍历有向图，形成一个森林（注意是森林），遍历时记下每个节点 i 所有子孙访问完成的时刻。如 i 有子孙a,b,c，则dfs(a), dfs(b), dfs(c)后将时间戳赋给 finish[i]。
2. 将所有边反向，构成新的图GT
3. 在GT上按点的时间戳降序做dfs，生成一个森林，每棵树就是一个强联通分量了。
强联通分量的性质：
1. 若 u,v 处于同一强联通分量中，则所有边反向后，它们任处在同一强联通分量中。
2. 在第二次 dfs 中，设点 u 的时间戳是当前所有未访问的点中最大的，则 u 所在的强联通分量 C 没有边指向其它未访问的强联通分量C'（注意是在G
T中）。因为若存在这样的边，则在G中存在边从 C' 的点指向 C，则C‘中点时间戳肯定比 u 大（回想一下第一次 dfs 时我们是怎样对点标时间戳的），与假设矛盾。
下面是代码，最后是测试文件。输出每个点属于哪个强联通分量。
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
const int maxn=100;
// 用于第一次dfs时记录每个点的finish时间戳
struct finish{
int id;
int ftime;
}f[maxn];
// 这个结构体用于第二次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访问标识数组
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");
// 根据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();
}
}
// 测试文件，包括两个图，第一个是联通的，第二个不联通
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