<题目链接>
题目大意：
有N(N<=10000)头牛，每头牛都想成为most poluler的牛，给出M(M<=50000)个关系，如(1,2)代表1欢迎2，关系可以传递，但是不可以相互，即1欢迎2不代表2欢迎1，但是如果2也欢迎3那么1也欢迎3.
给出N,M和M个欢迎关系，求被所有牛都欢迎的牛的数量。
解题分析：
仔细思考后发现，其实题目就是问你，在给出的这个有向图中的所有连通分量中，是否存在唯一出度为0的连通分量，如果存在，则输出这个连通分量中所有点的个数。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
using namespace std; #define pb push_back
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define clr(a,b) memset(a,b,sizeof(a))
const int N = 1e4+ , M = 5e4+; struct Edge{ int from,to,nxt; }e[M<<];
int n,m,cnt,tot,scc,top;
int stk[N],instk[N],head[N],dfn[N],low[N],bel[N],out[N]; inline void init(){
cnt=tot=scc=top=;
clr(head,-);clr(dfn,);clr(low,);clr(bel,);
clr(out,);clr(instk,);
}
inline void add(int u,int v){
e[++cnt]=(Edge){u,v,head[u]};head[u]=cnt;
}
void Tarjan(int u){
dfn[u]=low[u]=++tot;
instk[u]=,stk[++top]=u;
for(int i=head[u];~i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}else if(instk[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
++scc;
while(true){
int v=stk[top--];
instk[v]=;
bel[v]=scc;
if(v==u)break;
}
}
}
inline void Solve(){
rep(i,,cnt){
int u=e[i].from,v=e[i].to;
if(bel[u]!=bel[v]){
out[bel[u]]++; //统计每个强连通分量的出度
}
}
int num=,loc=-;
rep(i,,scc){
if(!out[i])num++,loc=i;
}
if(num==){
int ans=;
rep(i,,n) if(bel[i]==loc){
ans++;
}
printf("%d\n",ans);
}else puts("");
}
int main(){
while(~scanf("%d%d",&n,&m)){
init();
rep(i,,m){
int u,v;scanf("%d%d",&u,&v);
add(u,v);
}
rep(i,,n) if(!dfn[i]){
Tarjan(i);
}
Solve();
}
}
2018-08-16