[C++] 백준 10159번 : 저울

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

10159번: 저울

 

1. 접근 : 모든 정점에서 모든 정점으로 갈 수 있는지 판별 -> 플로이드와샬

가중치 없이 갈 수 있으면 true

 

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int N, M, a, b;
vector<int> g[101];
int d[101][101];

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	memset(d, 0, sizeof(d));

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		g[b].push_back(a);
		d[b][a] = 1;
	}

	for (int i = 1; i <= N; i++) {

		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) {
				if (i != j && i != k && j != k) {
					if (d[j][i] && d[i][k]) d[j][k] = 1;
				}
			}
		}

	}

	for (int i = 1; i <= N; i++) {
		int cnt = 0;
		for (int j = 1; j <= N; j++) {
			if (i != j && !d[i][j] && !d[j][i])
				cnt++;
		}
		cout << cnt << "\n";
	}

	return 0;
}