백준 바이러스 2606 C++

2606: 바이러스

바이러스에 감염된 컴퓨터의 개수는 세는 문제.

연결된 네트워크의 개수를 세면 된다.

입력으로 주어진 번호 쌍을 벡터에 넣어서 각 번호의 컴퓨터가 어떤 컴퓨터와 이어져있는지 정리한다.

그 후 1번 컴퓨터와 연결된 다른 컴퓨터의 개수를 세면 끝.

visited 변수를 잘 이용하여 이미 카운트 한 컴퓨터는 재탐색 하지 않도록 하는 것과 재귀함수를 이용하여 연결된 모든 컴퓨터를 탐색하는 것이 포인트.

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

int cnt = 0;
bool visited[101];
vector<int> v[101];

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

int main(){
	int c, n;
	cin >> c >> n;
	
	int a,b;
	for (int i=0;i<n;i++){
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1);

	cout << cnt;
}