백준10159 저울

작성일 | In

문제 링크

  • http://icpc.me/10159

문제 출처

  • 2014 지역 본선 초등4, 중등3, 고등2

사용 알고리즘

  • Floyd Warshall

시간복잡도

  • O(n3)

풀이

전형적인 플로이드 문제입니다.
a>b && b>c => a>c 라는 삼단 논법을 이용해 플로이드 알고리즘을 돌려주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>

int map[110][110];
int n, m;

int main(){
	scanf("%d %d", &n, &m);
	for(int i=0; i<m; i++){
		int a, b;
		scanf("%d %d", &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++){
				if(map[i][k]&&map[k][j]) map[i][j]=1;
			}
		}
	}
	for(int i=1; i<=n; i++){
		int cnt=0;
		for(int j=1; j<=n; j++){
			if(!map[i][j]&&!map[j][i]) cnt++;
		}
		printf("%d\n", cnt-1);
	}
}