백준2606 바이러스

작성일 | In

문제 링크

  • http://icpc.me/2606

문제 출처

  • 2004 지역 본선 초등3

사용 알고리즘

  • Floyd Warshall Algorithm

시간복잡도

  • O(n3)

풀이

전형적인 플로이드 문제입니다.
플로이드 알고리즘을 통해 1번 컴퓨터와 직/간접적으로 연결된 정점들을 모두 찾아주면 됩니다.

전체 코드

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

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