http://poj.org/problem?id=2186
题意：
一个有向图，求出点的个数（任意点可达）。
思路：
Kosaraju算法的第一次dfs是后序遍历，而第二次遍历时遍历它的反向图，从标号最大的结点开始遍历。
对于这道题，在求解强连通分量之后，能被所有点可达只可能是最后一个强连通块，根据遍历时的拓扑序，我们可以计算出最后一个的结点个数。
但是我们最后还是要判断一下，这个连通块是不是任意结点可达。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
using namespace std; const int maxn=+; int n,m;
vector<int> G[maxn];
vector<int> rG[maxn];
vector<int> vs; //后序遍历顺序的顶点列表
int vis[maxn];
int sccno[maxn]; //所属强连通分量的拓扑序
int scc_cnt; //强连通分量数量 void add_edge(int from,int to)
{
G[from].push_back(to);
rG[to].push_back(from);
} void dfs1(int u)
{
if(vis[u]) return;
vis[u]=;
for(int i=;i<G[u].size();i++) dfs1(G[u][i]);
vs.push_back(u);
} void dfs2(int u,int k)
{
if(sccno[u]) return;
sccno[u]=k;
for(int i=;i<rG[u].size();i++) dfs2(rG[u][i],k);
} void find_scc(int n)
{
scc_cnt=;
vs.clear();
memset(sccno,,sizeof(sccno));
memset(vis,,sizeof(vis));
for(int i=;i<n;i++) if(!vis[i]) dfs1(i);
for(int i=n-;i>=;i--)
if(!sccno[vs[i]]) dfs2(vs[i],++scc_cnt);
} int main()
{
//freopen("D:\\input.txt","r",stdin);
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=;i<m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
u--; v--;
add_edge(u,v);
}
find_scc(n);
int u=;
int ans=;
//计算出最后一个强连通分量中点的数量
for(int i=;i<n;i++)
{
if(sccno[i]==scc_cnt)
{
u=i;
ans++;
}
} //判断每个点是不是都能可达u
memset(sccno,,sizeof(sccno));
dfs2(u,);
for(int i=;i<n;i++)
{
if(sccno[i]==)
{
ans=;
break;
}
}
printf("%d\n",ans);
}
return ;
}