POJ-3180 : The Cow Prom
問題概要
分かりにくいけど、サイズ2以上の強連結成分の個数を求める問題。
解法
実際に強連結成分分解する。
acceptされたコード
#include <cstdio> #include <vector> #include <algorithm> using namespace std; void init() { int m; scanf("%d%d", &G.numV, &m); G.init(); for (int _ = 0; _ < m; ++_) { int from, to; scanf("%d%d", &from, &to); --from; --to; G.addDirectedEdge(from, to); } } int solve() { vector<int> componets; int n = calcStronglyConnectedComponent(G, componets); vector<int> cnts(n, 0); for (int v = 0; v < G.numV; ++v) { ++cnts[componets[v]]; } int ans = 0; for (int i = 0; i < n; ++i) if (cnts[i] >= 2) { ++ans; } return ans; } int main() { init(); printf("%d\n", solve()); return 0; }