思路：
建图时，分别建正向图edge和转置图T。用正向图edge来DFS，找出第一个被发现的强连通分支（如果该图存在题目要求的点，那么一定就是第一个被发现的）。然后用spfa跑转置图T，判断被发现的点是否可以到达所有点，如可以，就把该连通同的点数输出。否则输出0 。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define Maxn 10100
#define Maxm Maxn*10
#define inf 0x7fffffff
using namespace std;
int index[Maxn],vi[Maxn],stack[Maxn],dfn[Maxn],low[Maxn],e,n,lab,top,num,E,Index[Maxn],Que[];
struct Edge{
int from,to,next;
}edge[Maxm],T[Maxm];
void addedge(int from,int to)
{
edge[e].from=from;
edge[e].to=to;
edge[e].next=index[from];
index[from]=e++;
T[E].from=to;
T[E].to=from;
T[E].next=Index[to];
Index[to]=E++;
}
void init()
{
memset(index,-,sizeof(index));
memset(Index,-,sizeof(Index));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(vi,,sizeof(vi));
e=lab=top=num=E=;
}
void Out(int u)//统计该连通分量点的个数
{
int i,j;
do{
i=stack[--top];
num++;
vi[i]=;
}
while(i!=u);
}
int dfs(int u)
{
dfn[u]=low[u]=++lab;
stack[top++]=u;
vi[u]=;
int i,j,temp;
for(i=index[u];i!=-;i=edge[i].next)
{
temp=edge[i].to;
if(!dfn[temp])
{
if(dfs(temp))
return ;
low[u]=min(low[u],low[temp]);
}
if(vi[temp])
low[u]=min(low[u],dfn[temp]);
}
if(low[u]==dfn[u])//一旦找到就不在寻找了，这样省了很多时间。
{
Out(u);
return ;
}
return ;
}
int spfa(int u)//判断是否全图可达
{
memset(vi,,sizeof(vi));
int i,temp;
int head,tail;
head=tail=;
vi[u]=;
Que[head++]=u;
while(head!=tail)
{
temp=Que[tail++];
vi[temp]=;
for(i=Index[temp];i!=-;i=T[i].next)
{
if(!vi[T[i].to])
{
vi[T[i].to]=;
Que[head++]=T[i].to;
}
}
}
for(i=;i<=n;i++)
if(!vi[i])
return ;
return ;
}
int main()
{
int m,i,j,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for(i=;i<=m;i++)
{
scanf("%d%d",&a,&b);
addedge(a,b);
}
dfs();
if(spfa(stack[top]))
printf("%d\n",num);
else
printf("0\n");
}
return ;
}
在给个缩点的方法，将每次找到的连通分支全部标号为一样，这样每个连通分支就成了一个点，然后只要判断出度为0 的点的个数，如果只有一个，那么输出这个连通分量的点数，如果存在多个，则输出0 。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define Maxn 10100
#define Maxm Maxn*10
#define inf 0x7fffffff
using namespace std;
int index[Maxn],vi[Maxn],stack[Maxn],dfn[Maxn],low[Maxn],e,n,lab,top,num,list,ans[Maxn],degree[Maxn],be[Maxn];
struct Edge{
int from,to,next;
}edge[Maxm];
void addedge(int from,int to)
{
edge[e].from=from;
edge[e].to=to;
edge[e].next=index[from];
index[from]=e++;
}
void init()
{
memset(index,-,sizeof(index));
memset(degree,,sizeof(degree));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(vi,,sizeof(vi));
memset(ans,,sizeof(ans));
memset(be,,sizeof(be));
e=lab=top=num=list=;
}
void Out(int u)
{
int i,j;
list++;
do{
i=stack[--top];
be[i]=list;
num++;
vi[i]=;
}
while(i!=u);
ans[list]=num;
}
int dfs(int u)
{
dfn[u]=low[u]=++lab;
stack[top++]=u;
vi[u]=;
int i,j,temp;
for(i=index[u];i!=-;i=edge[i].next)
{
temp=edge[i].to;
if(!dfn[temp])
{
dfs(temp);
low[u]=min(low[u],low[temp]);
}
if(vi[temp])
low[u]=min(low[u],dfn[temp]);
}
if(low[u]==dfn[u])
Out(u);
return ;
}
int solve()
{
int i,j,temp,cc=;
for(i=;i<=n;i++)
if(!dfn[i])
dfs(i);
for(i=;i<=n;i++)
{
for(j=index[i];j!=-;j=edge[j].next)
{
temp=edge[j].to;
if(be[i]!=be[temp])
{
degree[be[i]]=;
}
}
}
for(i=;i<=list;i++)
{
if(!degree[i])
{
cc++;
temp=i;
}
}
if(cc==)
{
return ans[temp];
}
else
return ;
return ;
}
int main()
{
int m,i,j,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for(i=;i<=m;i++)
{
scanf("%d%d",&a,&b);
addedge(a,b);
}
printf("%d\n",solve());
}
return ;
}