Description
每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛,给你M对整数(A,B),表示牛A认为牛B受欢迎。 这
种关系是具有传递性的,如果A认为B受欢迎,B认为C受欢迎,那么牛A也认为牛C受欢迎。你的任务是求出有多少头
牛被所有的牛认为是受欢迎的。
Input
第一行两个数N,M。 接下来M行,每行两个数A,B,意思是A认为B是受欢迎的(给出的信息有可能重复,即有可
能出现多个A,B)
Output
一个数,即有多少头牛被所有的牛认为是受欢迎的。
Sample Input
3 3
1 2
2 1
2 3
1 2
2 1
2 3
Sample Output
1
Solution
这道题是裸的Tarjan。如果A认为B受欢迎那么B向A连边。先把每个强联通分量缩成点,然后枚举所有入度为0的强联通分量(注意单点也可以是强联通分量),bfs扫一遍看看可不可以从它到达所有其他强联通分量。如果可以到达那么答案就加上这个强联通分量的大小。
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;inline int read(){int xx=0,f=1;char ch=getchar();for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())xx=xx*10+ch-'0';return xx*f;
}const int maxn=10010,maxm=50010;
struct edge{int to,next;
}e[maxm],e2[maxm];
int n,m,cnt,ans,head[maxn],head2[maxn],num,num2,sta[maxn<<1],top;
int ltk[maxn],dfn[maxn],low[maxn],size[maxn],du[maxn];
bool vis[maxn];void add(int u,int v){e[++num].to=v;e[num].next=head[u];head[u]=num;
}
void add2(int u,int v){du[v]++;e2[++num2].to=v;e2[num2].next=head2[u];head2[u]=num2;
}
void dfs(int x){dfn[x]=low[x]=++cnt;sta[++top]=x;for(int i=head[x];i;i=e[i].next){if(!dfn[e[i].to]){dfs(e[i].to);low[x]=min(low[x],low[e[i].to]);}else if(!ltk[e[i].to]){low[x]=min(low[x],dfn[e[i].to]);}}if(dfn[x]==low[x]){ltk[0]++;while(top){ltk[sta[top]]=ltk[0];size[ltk[0]]++;if(sta[top--]==x)break;}}
}
void Rebuild(){for(int i=1;i<=n;i++){for(int j=head[i];j;j=e[j].next){if(ltk[i]!=ltk[e[j].to]){add2(ltk[i],ltk[e[j].to]);}}}
}
bool Work(int x){int tot=0,h=0;top=1;memset(sta,0,sizeof sta);memset(vis,0,sizeof vis);sta[top]=x;while(h<top){int now=sta[++h];vis[now]=true;tot++;for(int i=head2[now];i;i=e2[i].next){if(!vis[e2[i].to]){sta[++top]=e2[i].to;}}}for(int i=1;i<=ltk[0];i++){if(!vis[i]){return false;}}return true;
}int main(){n=read();m=read();for(int i=1,u,v;i<=m;i++){u=read();v=read();add(v,u);}for(int i=1;i<=n;i++){if(!dfn[i])dfs(i);}Rebuild();for(int i=1;i<=ltk[0];i++){if(!du[i]&&Work(i))ans+=size[i];}printf("%d\n",ans);return 0;
}