[백준 2606] 바이러스

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

2606번: 바이러스

서로 연결되어있는 점을 찾아 개수를 세는 문제이기 때문에 dfs로 풀어야한다고 생각했다. 컴퓨터의 수(n), 연결한 간선의 수(k)를 먼저 입력을 받고, k번만큼 연결된 노드 쌍을 입력받는다. 어떻게 입력받아야 할 지 고민했는데,

 

vector<int> list[101];

이렇게 vector로 list를 선언해서 해결했다.

 

 

답안

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

int cnt = 0;
vector<bool> visited(101);
vector<int> list[101];

void dfs(int x) {
	visited[x] = true;
	for (int i = 0; i < list[x].size(); i++) {
		int y = list[x][i];
		if (!visited[y]) {
			dfs(y);
			cnt++;
		}
	}
}

int main(void) {

	int n;
	cin >> n; // 노드 개수

	int k;
	cin >> k; // 엣지 개수

	while (k--) {
		int u, v;
		cin >> u >> v;
		list[u].push_back(v);
		list[v].push_back(u);
	}

	dfs(1);

	cout << cnt;

	return 0;
}