首页 > 代码库 > bzoj1051 [HAOI2006]受欢迎的牛
bzoj1051 [HAOI2006]受欢迎的牛
1051: [HAOI2006]受欢迎的牛
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 4773 Solved: 2541
[Submit][Status][Discuss]
Description
每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛,给你M对整数(A,B),表示牛A认为牛B受欢迎。 这
种关系是具有传递性的,如果A认为B受欢迎,B认为C受欢迎,那么牛A也认为牛C受欢迎。你的任务是求出有多少头
牛被所有的牛认为是受欢迎的。
Input
第一行两个数N,M。 接下来M行,每行两个数A,B,意思是A认为B是受欢迎的(给出的信息有可能重复,即有可
能出现多个A,B)
Output
一个数,即有多少头牛被所有的牛认为是受欢迎的。
Sample Input
3 3
1 2
2 1
2 3
1 2
2 1
2 3
Sample Output
1
HINT
100%的数据N<=10000,M<=50000
分析:对于这道题,可以很自然地想到强连通分量,为什么呢?因为如果答案只有1头牛,那么这头牛肯定在由自己一个点组成的强连通分量里,如果答案大于1,那么符合要求的牛必然在同一个强连通分量里,而且只有一个强连通分量符合要求,这个可以简单的证明一下:假设符合要求的强连通分量有n个,那么第n个强连通分量必然与第n-1个强连通分量联通,这样就组成了一个强连通分量,由此可类推符合要求的强连通分量只有1个.
根据这个,我们在统计答案的时候如果发现符合要求的强连通分量大于1个,那么就无解.怎么知道这个强连通是否符合要求呢?很简单,出度为0即可,如果出度不为0,那么这个“强连通分量”就是另外一个强连通分量的一部分,至于怎么找出度,dfs建图乱搞一下就好了.
#include <cstdio> #include <stack> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 10010, maxm = 50010; int n, m,head[maxn],to[maxm],nextt[maxm],tot,scc[maxn],dfsclock,low[maxn],pre[maxn],num,shuliang[maxn],ans; int head2[maxn], to2[maxn], nextt2[maxn], tot2; stack <int> s; void add(int x, int y) { tot++; to[tot] = y; nextt[tot] = head[x]; head[x] = tot; } void add2(int x, int y) { tot2++; to2[tot2] = y; nextt2[tot2] = head2[x]; head2[x] = tot2; } void tarjan(int u) { s.push(u); low[u] = pre[u] = ++dfsclock; for (int i = head[u];i;i = nextt[i]) { int v = to[i]; if (!pre[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (!scc[v]) low[u] = min(low[u], pre[v]); } if (low[u] == pre[u]) { num++; while (1) { int t = s.top(); s.pop(); scc[t] = num; shuliang[num]++; if (t == u) break; } } } void lianbian(int u) { for (int i = head[u]; i; i = nextt[i]) { int v = to[i]; if (scc[u] != scc[v]) add2(scc[u], scc[v]); } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int a, b; scanf("%d%d", &a, &b); add(a, b); } for (int i = 1; i <= n; i++) if (!scc[i]) tarjan(i); for (int i = 1; i <= n; i++) lianbian(i); for (int i = 1; i <= num; i++) if (!head2[i]) { if (ans) { printf("0\n"); return 0; } ans = shuliang[i]; } printf("%d\n", ans); return 0; }
bzoj1051 [HAOI2006]受欢迎的牛
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。