백준 2458번 : 키 순서 - 플로이드 와샬 알고리즘

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

2458번: 키 순서

1.문제설명

서로 키를 비교한 결과를 입력으로 주었을 때

 

키의 순서를 알 수있는 노드가 몇 개인지 구하는 문제이다.

 

2.접근방법

해당 노드의 키 순서를 알려면

 

해당 노드를 제외한 모든 노드와 비교가 되어야 한다.

 

플로이드 와샬 알고리즘으로 모든 노드간 거리를 구했을 때

 

만약 거리[a][b] 와 거리[b][a]가 모두 비교가 되지 않은 채 INF 값이 있다면

 

 a와 b는 순서를 알 수 없다.

 

 

 

 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;



int n, m, dist[501][501];

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

	memset(dist, 0x3f, sizeof(dist));

	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		dist[i][i] = 0;
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		dist[a][b] = 1;
	}


	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) {

		bool canKnow = true;
		for (int j = 1; j <= n; j++) {
			if (dist[i][j] > 10000) {
				if (dist[j][i] > 10000) {
					canKnow = false;
				}

			}
		}

		if (canKnow) ans++;

	}
	cout << ans << '\n';


	return 0;
}

백준 2458번