ProblemsSubmit ProblemOnline StatusProb.ID:
RegisterUpdate your infoAuthors ranklist
Current ContestPast ContestsScheduled ContestsAward ContestAshGuangr Log OutMail:2(0)Login Log ArchiveLanguage:Default
Popular Cows
Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 43975 Accepted: 17925Description
Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <= 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow.
Input
* Line 1: Two space-separated integers, N and M * Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular.
Output
* Line 1: A single integer that is the number of cows who are considered popular by every other cow.
Sample Input
3 3 1 2 2 1 2 3Sample Output
1Hint
Cow 3 is the only cow of high popularity.
Source
USACO 2003 Fall
题目大意:有n头牛,m个关系,表示为A牛认为B牛厉害,A-B A-C A也能到C,问有几头牛可以被所有牛认为厉害
题目思路:
一个强连通分量里的所有牛绝对会被其他认为厉害.
首先这个有向图需要联通,不连通的话,根本不存在.
其次 只要联通那么强连通分量之间具有单向关系,因为如果具有双向关系,是可以合并的.
所以 满足条件的点全部都在出度为0的强连通分量中.
1->2->3->4 那肯定选4 并且只能有一个出度为0 ,两个肯定还是不行.
具体代码:
//#include <bits/stdc++.h> #include<stdio.h> #include<vector> #include<queue> #include<string.h> #pragma GCC optimize(2) typedef long long ll; typedef unsigned long long ull; const int mod=1000; const int maxn=1e6+5; const ll INF=100000000000005; using namespace std; ll n,m,p; int head[maxn]; ll cnt=0; struct node{ int e,next; }edge[maxn]; int dfn[maxn],low[maxn];//dfs序号 他能连接到的最小根节点 int st[maxn],s=0;//栈 int sct[maxn],szsc[maxn],scc=0;//强连通分量所属,强连通分量个数 int inst[maxn];//标记是否在栈中 int out[maxn]; int pre[maxn]; int cot=0;//标记DFS序 void addedge(int u,int v) { edge[cnt].e=v; edge[cnt].next=head[u]; head[u]=cnt++; } void restart() { memset(head,-1,sizeof(head)); memset(low,0,sizeof(low)); memset(inst,0,sizeof(inst)); memset(dfn,0,sizeof(dfn)); memset(out,0,sizeof(out)); memset(szsc,0,sizeof(szsc)); s=0;scc=0;cot=0; cnt=0; } void Tarjan(int u) { st[++s]=u;inst[u]=1; low[u]=dfn[u]=++cot; for(int i=head[u];~i;i=edge[i].next) { int e=edge[i].e; if(!dfn[e]){ Tarjan(e); low[u]=min(low[u],low[e]); } else if(inst[e]) low[u]=min(low[u],dfn[e]); //else 被访问过并且不在栈里 那肯定已经为强连通分量了 } if(low[u]==dfn[u]){ scc++;//强连通分量++ while(1) { int x=st[s--]; inst[x]=0; sct[x]=scc; szsc[scc]++;//强连通分量的大小为1 if(u==x) break; } } } int Find(int x) { return pre[x]==x?x:pre[x]=Find(pre[x]); } void Merge(int x,int y) { int dx=Find(x); int dy=Find(y); if(dx!=dy) pre[dx]=dy; return; } int main() { while(~scanf("%lld%lld",&n,&m)) { restart(); for(int i=1;i<=n;i++) pre[i]=i; for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); addedge(x,y); Merge(x,y); } for(int i=1;i<=n;i++)if(!dfn[i]) Tarjan(i); for(int i=1;i<=n;i++) { for(int k=head[i];~k;k=edge[k].next) { int e=edge[k].e; if(sct[i]!=sct[e]) out[sct[i]]++; } } int f=0; int x=Find(1); for(int i=1;i<=n;i++)//判联通 { if(Find(i)!=x) { f=1; break; } } ll sum=0; int ok=0; for(int i=1;i<=scc;i++) { if(out[i]==0){ ok++; sum+=szsc[i]; } } if(ok==1&&!f) printf("%lld\n",sum); else printf("0\n"); } return 0; } /*** 样例测试空间: 6 5 1 2 2 3 3 1 3 5 2 6 ***/总结:开始图的连通性了.
