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;
}