题目描述:
每头奶牛都梦想着成为牧群中最受奶牛仰慕的奶牛。在牧群中,有N头奶牛,1≤N≤10,000,
给定M对(1≤M≤50,000)有序对(A, B),表示A仰慕B。由于仰慕关系具有传递性,也就是说,
如果A仰慕B,B仰慕C,则A也仰慕C,即使在给定的M对关系中并没有(A, C)。你的任务是
计算牧群中受每头奶牛仰慕的奶牛数量。
思路:
因为仰慕关系具有传递性,因此在同一个强连通分量中的顶点:如果强连通分量中一头牛A
受强连通分量外另一头牛B的仰慕,则该强连通分量中的每头牛都受B的仰慕;如果强连通分量
中一头牛A仰慕强连通分量外的另一头牛B,则强连通分量中的每一头牛都仰慕B。因此,本题
可以将强连通分量缩为一个顶点,并构造新图。最后作一次扫描,统计出度为0的顶点个数,如
果正好为1,则说明该顶点(可能是一个新构造的顶点,即对应一个强连通分量)能被其他所有
顶点走到,即该强连通分量为所求答案,输出它的顶点个数即可。
// 将上题代码改下Ok 了 缩点 求各点的出度
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <string.h>
using namespace std;
#define MOD 1000000007
#define maxn 60100
#define maxm 10010
struct Edge{
int to;
int next;
Edge(){};
Edge(int u,int v){to=u;next=v;}
}E[maxn];
stack<int> S;
int V[maxm],num;
int belong[maxm];
int pre[maxm];
int dfst,scc;
int ans;
//bool G[maxm][maxm];
int out[maxm];
void init(int n){
dfst=scc=0;
num=0;
ans=0;
while(!S.empty())
S.pop();
for(int i=1;i<=n;i++){
V[i]=-1;
pre[i]=0;
belong[i]=0;
}
}
void add(int u,int v){
E[num].to=v;
E[num].next=V[u];
V[u]=num++;
}
int tarjan(int u){
int lowu=pre[u]=++dfst;
int v,e;
S.push(u);
for(e=V[u];e!=-1;e=E[e].next){
v=E[e].to;
if(!pre[v]){
int lowv=tarjan(v);
lowu=min(lowu,lowv);
}
else if(!belong[v]) lowu=min(lowu,pre[v]);
}
if(lowu==pre[u]){
scc++;
for(;;){
int x=S.top();S.pop();
belong[x]=scc;
if(x==u) break;
}
}
return lowu;
}
int main()
{
int n,m,T;
int u,v;
int i,j=1;
//scanf("%d",&T);
while(scanf("%d %d",&n,&m)!=EOF){
init(n);
for(i=1;i<=m;i++){
scanf("%d %d",&u,&v);
add(u,v);
}
for(i=1;i<=n;i++)
if(!pre[i]) tarjan(i);
// for(i=1;i<=n;i++) printf("%d ",belong[i]);
for(i=1;i<=scc;i++) out[i]=0;
int e,u,v;
for(i=1;i<=n;i++)
{
for(e=V[i];e!=-1;e=E[e].next){
u=belong[i];
v=belong[E[e].to];
if(u!=v)
out[u]++;//,printf("v=%d ",v);
}
}
int flag=0,rc;
for(i=1;i<=scc;i++) if(!out[i]) flag++,rc=i;
if(flag!=1) {printf("0
");continue;}
flag=0;
// printf("?=%d ",rc);
for(i=1;i<=n;i++)
if(belong[i]==rc) flag++;
printf("%d
",flag);
}
return 0;
}