POJ 3180 The Cow Prom
题意:其实读懂题目就简单了,本质上就是求强连通分支点大于1的个数
思路:知道题意就简单了,直接强连通搞
代码:
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> #include <stack> using namespace std; const int N = 10005; int n, m; vector<int> g[N]; stack<int> S; int pre[N], dfn[N], dfs_clock, sccno[N], sccn, val[N]; void dfs_scc(int u) { pre[u] = dfn[u] = ++dfs_clock; S.push(u); for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (!pre[v]) { dfs_scc(v); dfn[u] = min(dfn[u], dfn[v]); } else if (!sccno[v]) dfn[u] = min(dfn[u], pre[v]); } if (dfn[u] == pre[u]) { sccn++; int cnt = 0; while (1) { cnt++; int x = S.top(); S.pop(); sccno[x] = sccn; if (x == u) break; } val[sccn] = cnt; } } void find_scc() { dfs_clock = sccn = 0; memset(pre, 0, sizeof(pre)); memset(sccno, 0, sizeof(sccno)); for (int i = 1; i <= n; i++) if (!pre[i]) dfs_scc(i); } int main() { while (~scanf("%d%d", &n, &m)) { for (int i = 1; i <= n; i++) g[i].clear(); int u, v; while (m--) { scanf("%d%d", &u, &v); g[u].push_back(v); } find_scc(); int ans = 0; for (int i = 1; i <= sccn; i++) if (val[i] > 1) ans++; printf("%d\n", ans); } return 0; }