P2341 [HAOI2006]受欢迎的牛/POJ2186:Popular Cows
题目背景
本题测试数据已修复。
题目描述
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶
牛都是自恋狂,每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜
欢B,B喜欢C,那么A也喜欢C。牛栏里共有N 头奶牛,给定一些奶牛之间的爱慕关系,请你
算出有多少头奶牛可以当明星。
输入输出格式
输入格式:
第一行:两个用空格分开的整数:N和M
第二行到第M + 1行:每行两个用空格分开的整数:A和B,表示A喜欢B
输出格式:
第一行:单独一个整数,表示明星奶牛的数量
输入输出样例
说明
只有 3 号奶牛可以做明星
【数据范围】
10%的数据N<=20, M<=50
30%的数据N<=1000,M<=20000
70%的数据N<=5000,M<=50000
100%的数据N<=10000,M<=50000
解题报告:
题目大意:给定一个有向图,求有多少个顶点是由任何顶点出发都可达的。
有用的定理:有向无环图中唯一出度为0的点,一定可 以由任何点出发均可达(由于无环,所 以从任何点出发往前走,必然终止于 一个出度为0的点)
思路:tarjan缩点,判断强联通分量的出度为0即可,若出度为0的联通分量的个数>1,则这些点互相不可到达,原问题无解,反之输出联通分量里的点数即可。
#include<bits/stdc++.h> #define N 100000 using namespace std; void in(int &x){ char c=getchar();x=0;int f=1; while(!isdigit(c)){if(c=='-') f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} x*=f; } struct node{ int to,next; }e[N]; int n,m,head[N],cnt,tot,dfn[N],low[N],item,belong[N],all[N],du[N]; stack<int>S; bool vis[N]; void add(int u,int v){ e[++tot].to=v;e[tot].next=head[u];head[u]=tot; } void tarjan(int u){ dfn[u]=low[u]=++item; S.push(u);vis[u]=1; for(int i=head[u],v;i,v=e[i].to;i=e[i].next){ if(!dfn[v]){ tarjan(v); low[u]=min(low[v],low[u]); }else if(vis[v]){ low[u]=min(low[u],dfn[v]); } }if(dfn[u]==low[u]){ int v=u;++cnt; do{ v=S.top();S.pop(); vis[v]=false; belong[v]=cnt;all[cnt]++; }while(v!=u); } } int main() { in(n);in(m); for(int i=1;i<=m;i++){ int u,v; in(u);in(v); add(u,v); }for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); //记录出度 for(int i=1;i<=n;i++){ for(int j=head[i],v;j,v=e[j].to;j=e[j].next){ if(belong[i]!=belong[v]){ du[belong[i]]++; } } } int an=0; for(int i=1;i<=cnt;i++){ if(!du[i]) { if(an) {puts("0");return 0;} an=i; } }printf("%d\n",all[an]); return 0; }