P2341 [HAOI2006]受欢迎的牛

 

题目大意

题面已经说的够明白了

我只是为了多一个标题，走走过场，好看QwQ

 

思路

题目明确给出的条件足够裸。既然牛的爱慕关系可以传递，那么自然地就想到了连通分量喽。只要是在同一个连通分量内的牛，它他们对整个局面造成的影响是一致的。那么就可以通过Tarjan算法进行缩点。所点后统计每个强连通分量的出度。如果只有一个出度为零的强连通分量（注意是强连通分量），那么这个点就是受欢迎的牛。如果存在两个以上的话，就证明它俩个都没有互相爱慕，那么肯定就不存在受欢迎的牛，所以直接输出0

 

吐槽一下

woc，Tarjan写错了都能刚出85分来，学到了学到了，我之前交的时候++Index写成了Index++。。。遛了遛了

 

代码

#include <iostream> #include <cstring> #include <cstdio> #include <stack> const int maxnode = 1e4+3; const int maxedge = 5e4+3; using namespace std; stack<int> S; int n, m, first[maxnode], next[maxedge], u[maxedge], v[maxedge], num[maxnode]; int low[maxnode], dfn[maxnode], Index, cnt, in[maxnode], Indgr[maxnode]; bool vis[maxnode]; inline int readInt() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while (c <= '9' && c >= '0') { x = x*10 + c-'0'; c = getchar(); } return x * f; } inline void addedge(int f, int i) { next[i] = first[f]; first[f] = i; } inline void Tarjan(int x) { low[x] = dfn[x] = ++Index; vis[x] = 1; S.push(x); int k = first[x]; while (k != -1) { if(!dfn[v[k]]) { Tarjan(v[k]); low[x] = min(low[x], low[v[k]]); } else if(vis[v[k]]) { low[x] = min(low[x], dfn[v[k]]); } k = next[k]; } if(dfn[x] == low[x]) { cnt++; while (!S.empty()) { int temp = S.top(); S.pop(); vis[temp] = 0; in[temp] = cnt; num[cnt]++; if(temp == x) break; } } } int main() { n = readInt(), m = readInt(); memset(first, -1, sizeof(first)); for(int i=1; i<=m; i++) { u[i] = readInt(); v[i] = readInt(); addedge(u[i], i); } for(int i=1; i<=n; i++) { if(!dfn[i]) Tarjan(i); } for(int i=1; i<=n; i++) { int k = first[i]; while (k != -1) { if(in[v[k]] != in[u[k]]) Indgr[in[u[k]]]++; k = next[k]; } } int mark = 0; for(int i=1; i<=cnt; i++) { if(Indgr[i] == 0) { if(mark) { printf("0\n"); return 0; } mark = i; } } printf("%d", num[mark]); }

 

转载于:https://www.cnblogs.com/bljfy/p/9326200.html

相关资源：数据结构—成绩单生成器