链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1051
思路: 首先用Tarjan把环缩成点,要想收到所有人的欢迎,那么这个点的出度必为0,且只能有一个出度为0的,如果有多个的话那么没有点会收到所有人欢迎,我们找到这个点,这个点可能是缩完点后的点,我们找下这个点代表的环中点的数量。
实现代码:
#include<bits/stdc++.h>
using namespace std; const int M = 5e4+;
vector<int>g[M];
stack<int>s;
int dfn[M],low[M],vis[M],in[M],out[M],cnt,num,scc[M];
void Tarjan(int u){
dfn[u] = low[u] = ++cnt;vis[u] = ;
s.push(u);
for(int i = ;i < g[u].size();i ++){
int v = g[u][i];
if(!vis[v]) Tarjan(v),low[u] = min(low[u],low[v]);
else low[u] = min(low[u],dfn[v]);
}
if(low[u] == dfn[u]){
num++; int now;
do{
now = s.top(); s.pop();
scc[now] = num;
} while(!s.empty()&&now!=u);
}
} int main()
{
int n,m,u,v;
scanf("%d%d",&n,&m);
for(int i = ;i <= m;i ++){
scanf("%d%d",&u,&v);
g[u].push_back(v);
}
for(int i = ;i <= n;i ++){
if(!vis[i]) Tarjan(i);
}
for(int i = ;i <= n;i ++){
for(int j = ;j < g[i].size();j ++){
int v = g[i][j];
if(scc[i] != scc[v]){
out[scc[i]]++;
in[scc[v]]++;
}
}
}
int k = ,ans = ,tag;
for(int i = ;i <= num;i ++){
if(!out[i]){
k++; tag = i;
}
}
if(k == ){
for(int i = ;i <= n;i ++)
if(scc[i] == tag) ans++;
printf("%d\n",ans);
}
else printf("0\n");
return ;
}