本题让求有多少点 是图中所有点都可到达改点的
定理:在一个有向图中,如果有一个节点的出度为0,并且仅有一个这样的点,则该图中所有的点都可到达该点
先求出图的强连通分量,然后将每个强连通分量化为一个层次,求是否存在一个强连通分量,该分量的出度为一,并且仅有一个这样的分量,则该连通分量中的点都是满足条件的,输出该连通分量的点的个数;如果不存在,则输出0;
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
#include<stdlib.h>
#include<vector>
using namespace std;
vector<int> q[10010];
int dfn[10010],low[10010],f[10010],ceng[10010],du[10010];//ceng[]表示每个点所在的强连通分量的层数,du[]表示每个连通分量的出度
stack<int> z;
int ntime,nceng;
void Tarjan(int u) //求强连通分量模板
{
dfn[u]=low[u]=++ntime;
z.push(u);
f[u]=1;
int i,v;
for(i=0;i<q[u].size();i++) {
v=q[u][i];
if (!dfn[v])
{
Tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (f[v]==1)
{
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u])
{
while(1)
{
v=z.top();
z.pop();
f[v]=0;
ceng[v]=nceng;
if(v==u){
nceng++;
break;
}
}
}
}
int main()
{
int i,j,k;
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
for(i=1;i<=n;i++){ //初始化
q[i].clear();
dfn[i]=0;
low[i]=0;
ceng[i]=0;
du[i]=0;
f[i]=0;
}
while(!z.empty())
z.pop();
while(m--){
int a,b;
scanf("%d%d",&a,&b);
q[a].push_back(b);
}
ntime=1;
nceng=1;
for(i=1;i<=n;i++)
if(dfn[i]==0)//如果该点没有遍历过,则遍历该点
Tarjan(i);
for(i=1;i<=n;i++){
for(j=0;j<q[i].size();j++){
int v=q[i][j];
if(ceng[i]!=ceng[v])//如果i点和v点的层数不一样,则他们属于两个连通分量,则i的出度加1.
du[ceng[i]]++;
}
}
int flag,sum=0; //sum记录有几个出度为0的连通分量,flag记录该分量的层数
for(i=1;i<nceng;i++){
if(du[i]==0){
flag=i;
sum++;
}
}
if(sum!=1){ //如果出度为0 的连通分量不等于1,则输出0
printf("0\n");
}
else{
int ans=0;
for(i=1;i<=n;i++)//计算该层数的点的个数
if(ceng[i]==flag)
ans++;
printf("%d\n",ans);
}
}
system("pause");
return 0;
}