알고리즘/백준
[백준/C,C++] 2606번: 바이러스
이민훈
2021. 5. 5. 02:54
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
풀이
1번을 기준으로 DFS나 BFS를 돌려주기만 하면 되는 문제입니다.
#include<iostream>
#include<vector>
using namespace std;
const int MAX = 101;
vector<int> v[MAX];
bool visited[MAX];
int res = -1;
void DFS(int node)
{
res++;
visited[node] = true;
size_t sz = v[node].size();
for (size_t i = 0; i < sz; i++) {
int next = v[node][i];
if (!visited[next]) DFS(next);
}
return;
}
int main(void)
{
int n, m; cin >> n >> m;
while (m--) {
int i, j; cin >> i >> j;
v[i].push_back(j);
v[j].push_back(i);
}
DFS(1);
cout << res;
return 0;
}반례
Input
2
1
1 2
Output
1
Input
8
7
1 2
2 3
3 4
4 1
5 6
6 7
7 8
Output
3