描述
http://www.lydsy.com/JudgeOnline/problem.php?id=1612
(n)头奶牛比赛,给出一些胜负情况,问可以确定多少头奶牛的排名.
分析
无论胜负,只要知道某一头奶牛和其他(n-1)头的关系就好了.
我们用dfs来求每一个奶牛赢了多少次,同时统计那些输了的.
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn=100+5; 5 int n,m,ect,ans; 6 int win[maxn],los[maxn],head[maxn]; 7 bool vis[maxn]; 8 struct edge{ 9 int to,next; 10 edge(int to=0,int next=0):to(to),next(next){} 11 }g[maxn*maxn]; 12 inline int read(int &x){ x=0;int k=1;char c;for(c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')k=-1;for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';return x*=k; } 13 inline void add_edge(int u,int v){ g[++ect]=edge(v,head[u]); head[u]=ect; } 14 int dfs(int x){ 15 los[x]++; vis[x]=true; 16 int s=1; 17 for(int i=head[x];i;i=g[i].next)if(!vis[g[i].to]) s+=dfs(g[i].to); 18 return s; 19 } 20 int main(){ 21 read(n); read(m); 22 for(int i=1,u,v;i<=m;i++){ 23 read(u); read(v); 24 add_edge(u,v); 25 } 26 for(int i=1;i<=n;i++){ 27 memset(vis,false,sizeof vis); 28 los[i]--; 29 win[i]=dfs(i)-1; 30 } 31 for(int i=1;i<=n;i++)if(win[i]+los[i]==n-1) ans++; 32 printf("%d ",ans); 33 return 0; 34 }