[BOJ/C++] 2606 바이러스 : DFS

문제

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

풀이

DFS : 재귀함수로 구현
vector로 인접리스트 생성-> 재귀적으로 순회

인접리스트 생성
ex)
1 2
2 3
1 5
5 2
5 6
4 7

v[a].push_back(b);
v[b].push_back(a);

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> v[101]; //인접 리스트
bool check[101];
int ans = 0;

void dfs(int node) {
	check[node] = true;

	for (int i = 0; i < v[node].size(); i++) {
		int next = v[node][i];

		if (!check[next]) {
			dfs(next);
			ans++;
		}
	}
}


int main() {
	int a, b; //a:노드 개수, b:엣지 개수

	cin >> a >> b;
	for (int i = 0; i < b; i++) {
		int tmp1, tmp2;

		cin >> tmp1 >> tmp2;

		/* 인접 리스트 생성 */
		v[tmp1].push_back(tmp2);
		v[tmp2].push_back(tmp1);
	}

	dfs(1);
	cout << ans << '\n';

	return 0;
}