백준 10159 c++ "저울" -[PlusUltraCode]

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

10159번: 저울

[필자 사고 ]

전형적인 플로이드 와샬을 이용하면 쉽게 해결할 수 있는 문제이다.

 

다만 알고리즘을 적용만 하면 답이 나오는 것이 아닌 이 문제의 특이한점은 순위가 결정 됬냐 안됬냐 하는 점이다.

 

만약 1->4 의 값이 자연수이고 4->1의 값은 무한대라고 했을 때 1과 4의 관계는 순위가 정해졌다고 말할 수 있따.

 

다만 플로이드 와샬 알고리즘을 적용하면 저런 형태로 나온다.

 

즉 우리는 플로이드 와샬 알고리즘을 한번 사용하고 그 후 작업을 따로 해줬다. 

 

"만약 1->4의 값이 자연수이면 4->1의 값은 자연수로 저장해 놓는다."

 

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> Arr;
int N, M;

const int INF = 987654321;

void Input() {
	cin >> N >> M;
	Arr.resize(N + 1);
	for (int i = 0; i <= N; i++) {
		Arr[i].resize(N + 1,INF);
	}
	for (int i = 0; i < M; i++) {
		int s, e;
		cin >> s >> e;
		Arr[s][e] = 1;
	}
	for (int i = 0; i <= N; i++) {
		Arr[i][i] = 0;
	}
}

void Floyd_Warshall() {
	for (int k = 1; k <= N; k++) {
		for (int s = 1; s <= N; s++) {
			for (int e = 1; e <= N; e++) {
				Arr[s][e] = min(Arr[s][e], Arr[s][k] + Arr[k][e]);
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= N; k++) {
			if (Arr[i][k] != INF) {
				Arr[k][i] = 1;
			}
		}
	}
}

int main(void) {
	Input();
	Floyd_Warshall();
	for (int i = 1; i <= N; i++) {
		int count = 0;
		for (int k = 1; k <= N; k++) {
			if (Arr[i][k] == INF) {
				count++;
			}
		}
		cout << count << '\n';
	}
}