受欢迎的牛【tarjan】【强连通分量】

受欢迎的牛【tarjan】【强连通分量】

>Link

ybtoj受欢迎的牛

luogu P2341

>解题思路

一开始我是想到用拓扑，按拓扑序依次累计上每头牛的追求者数目，最后计算答案
这样就需要先找出入度为0的点开头，但是发现图中可能没有入度为0的点……所以我们需要找出强连通分量进行缩点，使图变成 有向无环图，这样就一定会有入度为0的点了。这样做是成立的，因为强连通中的点可以两两到达，如果其中一个点可以到达分量外的点，那么强连通分量中的另一个点也一定可以到达这个点，相反依然成立。

但是不知道为什么我WA 了，后来我去看书，发现了更简单的做法
缩点之后会形成一个新图，记录下每个点的出度，如果有一个点的出度为0，那么这个点就是“明星”；如果有多个点出度为0，那么就没有“明星”

>代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#define N 50010 
using namespace std;stack<int> st;
queue<int> Q;
struct edge
{int to, next;
} e[N];
int n, m, h[N], hcnt, c[N], k;
int dfn[N], low[N], cnt, col[N], tot, sum[N];void tarjan (int now)
{dfn[now] = low[now] = ++cnt;st.push(now);for (int i = h[now]; i; i = e[i].next){int v = e[i].to;if (!dfn[v]){tarjan (v);low[now] = min (low[now], low[v]);}else if (!col[v])low[now] = min (low[now], low[v]);}if (dfn[now] == low[now]){col[now] = ++tot;sum[tot] = 1;while (st.top() != now){p()] = tot;sum[tot]++;st.pop();}st.pop();}
}int main()
{scanf ("%d%d", &n, &m);for (int i = 1; i <= m; i++){int u, v;scanf ("%d%d", &u, &v);e[++hcnt] = (edge){v, h[u]};h[u] = hcnt;}for (int i = 1; i <= n; i++)if (!dfn[i]) tarjan (i);for (int uu = 1; uu <= n; uu++)for (int i = h[uu]; i; i = e[i].next){int u = col[uu], v = col[e[i].to];if (u == v) continue;c[u]++;}for (int i = 1; i <= tot; i++)if (!c[i]){if (k == 0) k = i;else k = -1;}if (k > 0) printf ("%d", sum[k]);else printf ("0");return 0;
}