2458 키 순서

플로이드 와샬 문제지만, 노드 간의 거리를 굳이 알 필요는 없고 연결 유무만 알면 된다. 플로이드 와샬을 쓰는 이유는 모든 정점에서의 최단 경로를 알 수 있기 때문이다. 플로이드 와샬을 구했다면 어떻게 순서를 알 수 있는 것일까?

1. 어느 한 노드를 잡아본다

2. 나머지 노드간의 관계에서 연결된 노드가 있다면 이 노드는 순서를 알 수 없다

3. 왜냐하면 순서를 명확히 알 수 있다면 자신에서 나가는 노드의 합과 들어오는 노드의 합이 반드시 N-1이어야만 한다

 

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

깃허브주소: https://github.com/surinoel/boj/blob/master/2458.cpp

 

	#include <cstring>
	#include <iostream>
	#include <algorithm>
	using namespace std;
	int d[501][501];
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	fill(&d[0][0], &d[n][n + 1], 1e5);
	for (int i = 0; i < m; i++) {
	int x, y;
	cin >> x >> y;
	d[x][y] = 1;
	}
	for (int k = 1; k <= n; k++) {
	for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
	if (d[i][j] > d[i][k] + d[k][j]) {
	d[i][j] = d[i][k] + d[k][j];
	}
	}
	}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
	bool ok = true;
	for (int j = 1; j <= n; j++) {
	if (i == j) continue;
	if (d[i][j] == 1e5 && d[j][i] == 1e5) {
	ok = false;
	break;
	}
	}
	if (ok) ans += 1;
	}
	cout << ans << '\n';
	return 0;
	}

view raw 2458.cpp hosted with ❤ by GitHub