用adj作為鄰接表，存正向的邊，把邊反向存在adj_op里。
第一次dfs1確定一顆深度優(yōu)先搜索樹(shù)，用finish記錄訪(fǎng)問(wèn)順序，然后從finish后面往前進(jìn)行dfs2，每一次dfs2可以確定一個(gè)強(qiáng)連通分量。
證明參考算法導(dǎo)論
#include<iostream>
#include<vector>
using namespace std;
const int MAX=10005;
vector<int>adj[MAX], adj_op[MAX];
bool visit[MAX]={0},out[MAX];
int sblg[MAX],n,m;
vector<int> finish;
void dfs1(int i)
{
if(visit[i])return ;
visit[i]=true;
for(int k=0; k<adj[i].size(); k++)
if(!visit[adj[i][k]])dfs1(adj[i][k]);
finish.push_back(i);
}
void dfs2(int i, int c)
{
if(visit[i])return ;
visit[i]=true;
sblg[i]=c;
for(int k=0; k<adj_op[i].size(); k++)
if(!visit[adj_op[i][k]])dfs2(adj_op[i][k],c);
}
int main()
{
while(cin>>n>>m)
{
memset(visit,0,sizeof visit); memset(out,0,sizeof out); memset(sblg,0,sizeof sblg);
for(int i=1; i<=n; i++){ adj[i].clear(); adj_op[i].clear(); }
int u,v;
for(int i=1; i<=m; i++)
{
cin>>u>>v;
adj[u].push_back(v);
adj_op[v].push_back(u);
}
for(int i=1; i<=n; i++)
if(!visit[i])dfs1(i);
memset(visit,0,sizeof visit);
int cnt=0;
for(int i=finish.size()-1; i>=0; i--)
{
if(!visit[finish[i]])
{
cnt++;
dfs2(finish[i],cnt);
}
}
for(int i=1; i<=n; i++)
{
for(int j=0; j<adj[i].size(); j++)
{
if(sblg[i]!=sblg[adj[i][j]])out[sblg[i]]=true;
}
}
int count=0,index=0,num=0;
for(int i=1; i<=cnt; i++)
if(out[i]==0){ count++;index=i; }
//for(int i=1; i<=n; i++)
// cout<<sblg[i]<<endl;
if(count==1)
{
for(int i=1; i<=n; i++)
if(sblg[i]==index)num++;
cout<<num<<endl;
}
else cout<<0<<endl;
}
return 0;
}