알고리즘 문제
[C/C++ 백준 2606번] 바이러스 (Silver 3)
새파란 공대생
2020. 9. 22. 23:22
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어��
www.acmicpc.net
DFS와 BFS 중 어느 방법을 써도 상관 없을듯.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int cnt = 0;
void search(vector <int> graph[], bool visit[], int start){
visit[start]=true;
cnt++;
for(int i=0; i<graph[start].size(); i++){
if(visit[graph[start][i]]==false){
visit[graph[start][i]]=true;
search(graph, visit, graph[start][i]);
}
}
}
int main(void){
int N, M, a, b;
scanf("%d %d", &N, &M);
vector <int> graph[N+1];
bool visit[N+1];
for(int i=1; i<=N; i++)
visit[i] = false;
for(int i=0; i<M; i++){
scanf("%d %d", &a, &b);
graph[a].push_back(b);
graph[b].push_back(a);
}
search(graph, visit, 1);
printf("%d", cnt-1);
}