C++ / 백준 / 6156 / Cow Contest

문제

 

https://www.acmicpc.net/problem/6156

6156번: Cow Contest

 

문제풀이

 

플로이드 워셜 알고리즘을 이용해 풀었다.

소의 등수를 알려면 소가 다른 소한테 이기든 지든 모든 소에 대해 결과를 알아야 한다.

따라서 최단 거리를 구해 다른 소와 모두 연결된 소의 개수를 세면 된다.

 

코드

#include <iostream>
#include <vector>
#define INF 4501
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N(0), M(0);
	cin >> N >> M;

	vector<vector<int>>dist(N + 1, vector<int>(N + 1, INF));

	for (int cow = 0; cow <= N; ++cow) {
		dist[cow][cow] = 0;
	}

	int cow1(0), cow2(0);
	for (int idx = 0; idx < M; ++idx) {
		cin >> cow1 >> cow2;
		dist[cow1][cow2] = 1;
	}

	for (int mid = 1; mid <= N; ++mid) {
		for (cow1 = 1; cow1 <= N; ++cow1) {
			for (cow2 = 1; cow2 <= N; ++cow2) {
				dist[cow1][cow2] = min(dist[cow1][cow2], dist[cow1][mid] + dist[mid][cow2]);
			}
		}
	}

	int answer(0);
	for (cow1 = 1; cow1 <= N; ++cow1) {
		int count(0);
		for (cow2 = 1; cow2 <= N; ++cow2) {
			if (dist[cow1][cow2] != INF || dist[cow2][cow1] != INF) {
				++count;
			}
		}
		if (count == N) ++answer;
	}
	cout << answer;
}