[C/C++] 백준 10159번 - 저울 (플루이드 와샬)

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int n, m, u, v;
bool arr[101][101];

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

	cin >> n;
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> u >> v;
		arr[u][v] = true;
	}

	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (arr[i][k] && arr[k][j])
					arr[i][j] = true;

	for (int i = 1; i <= n; i++)
	{
		int cnt = 0;
		for (int j = 1; j <= n; j++)
			if (arr[i][j] == 0 && arr[j][i] == 0) cnt++;
		cout << cnt - 1 << '\n';
	}
}

 

풀이 방법

 

예제입력1 결과 arr배열

 

플로이드 와샬로 연결관계들을 저장해주고

arr[i][j] 와 arr[j][i] 둘다 0이라면 연결관계가 아예 없는 것이므로 카운트해줍니다.

 

 

www.acmicpc.net/problem/10159

10159번: 저울