题意：给定一个有向图，求有多少顶点可以通过任意一个顶点到达 ； 顶点数《=10,000 边数《=50,000;
解析：有向无环图中出度为0且唯一，则该点即可通过任意一点到达；
1.求出所有的强连通分量，用Korasaju算法
2.每个强连通分量缩成一点，则形成一个有向无环图DAG。
3.DAG上面如果有唯一的出度为0的点，则该点能被所有的点可达。
那么该点所代表的连通分量上的所有的原图中的点，都能被原图中
的所有点可达 ，则该连通分量的点数就是答案。
4.DAG上面如果有不止一个出度为0的点，则这些点互相不可达，原问题
无解，答案为0；
（此外DAG肯定是一个有向无环图，则至少存在一个出度为0的点，上面
两种情况包括了所有可能。
#include<iostream> #include<algorithm> #include<stdio.h> #include<stdlib.h> #include<string.h> #define maxn 10010 //head1,head2分别用来存储正图和逆图的头结点 int head1[maxn],head2[maxn]; //Et表示每个点搜索结束的时间，ss表示每个连通分量的点的个数 int mark1[maxn],mark2[maxn],Et[maxn],ss[maxn]; int con1,p,q,con2,num; //du表示统计出入度的个数，vis标记数组 int vis[maxn],du[maxn]; //edge1存原图,edge2存逆图; struct node { int to,next; } edge1[maxn*5],edge2[maxn*5]; //E存边 struct edge { int u,v; } E[maxn*5]; void Init()//初始化 { memset(du,0,sizeof(du)); memset(mark1,0,sizeof(mark1)); memset(mark2,0,sizeof(mark2)); memset(head1,-1,sizeof(head1)); memset(head2,-1,sizeof(head2)); memset(Et,0,sizeof(Et)); p=q=con1=con2=1; } void add(int a,int b)//建立邻接表; { edge1[p].to=b; edge1[p].next=head1[a],head1[a]=p++; edge2[q].to=a; edge2[q].next=head2[b],head2[b]=q++; } void DFS1(int u)//深度搜索原图 { mark1[u]=1; for(int i=head1[u]; i!=-1; i=edge1[i].next) if(!mark1[edge1[i].to]) DFS1(edge1[i].to); Et[con1++]=u;//按照完成时间从小到大存入 } void DFS2(int u) //深度搜索逆图 { mark2[u]=1; num++; vis[u] = con2; for(int i=head2[u]; i!=-1; i=edge2[i].next) { if(!mark2[edge2[i].to]) DFS2(edge2[i].to); } } int main() { int i,a,b,n,m; while(scanf("%d%d",&n,&m)!=EOF) { Init(); for(i=1; i<=m; i++) { scanf("%d%d",&a,&b); E[i].u=a,E[i].v=b; add(a,b); } for(i=1; i<=n; i++) if(!mark1[i]) DFS1(i); for(i=con1-1; i>=1; i--) { if(!mark2[Et[i]]) { num=0; DFS2(Et[i]); ss[con2++]=num; } } int j,sum=0; for(i=1; i<=m; i++) if(vis[E[i].u] != vis[E[i].v])//判断原图的边是否属于同一分支，即点数; du[vis[E[i].u]]++; for(i=1; i<con2; i++)//计算出度为0的个数 { if(!du[i]) { sum++; j=i; } } if(sum>1) printf("0 "); else printf("%d ",ss[j]); } return 0; }