[백준] 10159번 : 저울

문제

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

10159번: 저울

문제해결

플로이드-워셜 알고리즘

결과

소스코드

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

const int LM = 105;
int map[LM][LM];
int ans[LM];
int n, m;

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

	cin >> n;
	cin >> m;

	while (m--)
	{
		int a, b;
		cin >> a >> b;
		map[a][b] = 1;
	}

	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				map[i][j] = max(map[i][j], (map[i][k]&map[k][j]));
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i!=j && map[i][j] == 0 && map[j][i]==0)
			{
				ans[i]++;
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		cout << ans[i] << "\n";
	}
	return 0;
}