C언어 문제풀이

백준 2606번: 바이러스 (bfs 이용)

지식보부상님 2024. 1. 12. 19:38

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

 

2606번: 바이러스

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍

www.acmicpc.net

#include <stdio.h>

int graph[101][101] = { 0, };
int queue[10001] = { 0, };
int visited[101] = { 0, };
int n = 0;
int ans = 0;

void bfs() {
	int front = 0, rear = 0;
	int w;

	queue[rear++] = 1;
	visited[1] = 1;

	while (front < rear) {
		int v = queue[front++];
		
		for (w = 1; w <= n; w++) {
			if (graph[v][w] && !visited[w]) {
				queue[rear++] = w;
				visited[w] = 1;
				ans++;
			}
		}
	}
}


int main() {
	int  e;
	int w1, w2;

	scanf("%d", &n);
	scanf("%d", &e);

	for (int i = 1; i <= e; i++) {
		scanf("%d %d", &w1, &w2);
		graph[w1][w2] = 1;
		graph[w2][w1] = 1;
	}

	bfs();
	printf("%d", ans);

	return 0;
}