图论-Tarjan
dfn[u]表示dfs时达到顶点u的次序号（时间戳），low[u]表示以u为根节点的dfs树中次序号最小的顶点的次序号，所以当dfn[u]=low[u]时，以u为根的搜索子树上所有节点是一个强连通分量。 先将顶点u入栈，dfn[u]=low[u]=++idx,扫描u能到达的顶点v，如果v没有被访问过，则dfs(v)，low[u]=min(low[u],low[v])，如果v在栈里，low[u]=min(low[u],dfn[v])，扫描完v以后，如果dfn[u]=low[u]，则将u及其以上顶点出栈。
图片和邻接表版本代码转自：five20
注意：vector邻接表与链式前向星有内存性能上的差异，因为vector扩充时是默认多申请50%的内存空间，所以一些特别变态的题目可能会卡内存只能用链式前向星的写法写。
链式前向星版本：
#include <cstdio>
#include <stack>
#include <cstring>
#include <iostream>
using namespace std
;
int n
,m
,idx
=0,k
=1,Bcnt
=0;
int head
[100];
int ins
[100]={0};
int dfn
[100]={0},low
[100]={0};
int Belong
[100];
stack
<int> s
;
struct edge
{
int v
,next
;
}e
[100];
int min(int a
,int b
)
{
return a
<b
?a
:b
;
}
void adde(int u
,int v
)
{
e
[k
].v
=v
;
e
[k
].next
=head
[u
];
head
[u
]=k
++;
}
void readdata()
{
int a
,b
;
memset(head
,-1,sizeof(head
));
scanf("%d%d",&n
,&m
);
for(int i
=1;i
<=m
;i
++)
{
scanf("%d%d",&a
,&b
);
adde(a
,b
);
}
}
void tarjan(int u
)
{
int v
;
dfn
[u
]=low
[u
]=++idx
;
s
.push(u
);/将u入栈
ins
[u
]=1;/标记u在栈内
for(int i
=head
[u
];i
!=-1;i
=e
[i
].next
)
{
v
=e
[i
].v
;
if(!dfn
[v
])/如果v没被处理过
{
tarjan(v
);/dfs(v
)
low
[u
]=min(low
[u
],low
[v
]);
}
else if(ins
[v
]) low
[u
]=min(low
[u
],dfn
[v
]);
}
if(dfn
[u
]==low
[u
])
{
Bcnt
++;
do
{
v
=s
.top();
s
.pop();
ins
[v
]=0;
Belong
[v
]=Bcnt
;
}while(u
!= v
);
}
}
void work()
{
for(int i
=1;i
<=n
;i
++) if(!dfn
[i
])tarjan(i
);
printf("\n");
for(int i
= 1;i
<= 6;i
++)printf("%d %d\n",dfn
[i
],low
[i
]);
printf("共有%d强连通分量，它们是:\n",Bcnt
);
for(int i
=1;i
<=Bcnt
;i
++)
{
printf("第%d个:",i
);
for(int j
=1;j
<=n
;j
++)
{
if(Belong
[j
]==i
)printf("%d ",j
);
}
printf("\n");
}
}
int main()
{
readdata();
work();
return 0;
}
vector邻接表版本
#include<iostream>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std
;
vector
<int> Edge
[10005];
int dfn
[10005],low
[10005],index
,vis
[10005],cnt
,ans
;
stack
<int> S
;
void tarjan(int u
)
{
dfn
[u
]=low
[u
]=++index
;
vis
[u
]=1;
S
.push(u
);
for(int i
=0;i
<Edge
[u
].size();i
++)
{
int v
= Edge
[u
][i
];
if(!dfn
[v
])
{
tarjan(v
);
low
[u
] = min(low
[u
],low
[v
]);
}
else if(vis
[v
])
low
[u
] = min(low
[u
],dfn
[v
]);
}
if(dfn
[u
]==low
[u
])
{
int now
,cnt
=0;
while(1)
{
cnt
++;
now
= S
.top();
S
.pop();
vis
[now
] = 0;
if(now
==u
)
break;
}
if(cnt
>1)
ans
++;
}
}
int main()
{
int m
,n
,a
,b
;
cin
>> n
>> m
;
while(m
--)
{
cin
>> a
>> b
;
Edge
[a
].push_back(b
);
}
for(int i
=1;i
<=n
;i
++)
{
if(!dfn
[i
])
tarjan(i
);
}
cout
<< ans
;
return 0;
}
