Graph 상의 완전 탐색
DFS를 이용해 완전 탐색
BFS를 이용해도 OK!
// link: https://www.acmicpc.net/problem/2606
#include <iostream>
#include <vector>
int gDfsAnswer = 0;
void DFS(const std::vector<std::vector<bool>>& graph, std::vector<bool>& visit, const int n, const int current){
//not visited
// -> increase gDfsAnswer
// -> do DFS recursively
++gDfsAnswer;
visit[current] = true;
for (int i=1; i<=n; ++i){
if ((graph[current][i]) && (!visit[i])){
DFS(graph, visit, n, i);
}
}
}
int CalculateVirusComputer(const std::vector<std::vector<bool>>& graph, const int n){
int answer = 0;
//make visit
std::vector<bool> visit(n+1, false);
DFS(graph, visit, n, 1);
answer = gDfsAnswer-1;
//-1: to ignore starting point 1
return answer;
}
int main(){
int n = 0;
int k = 0;
std::cin >> n;
std::cin >> k;
std::vector<std::vector<bool>> graph(n+1, std::vector<bool>(n+1, false));
//ignore 0-th
for (int i=0; i<k; ++i){
int from = 0;
int to = 0;
std::cin >> from >> to;
graph[from][to] = true;
graph[to][from] = true;
}
std::cout << CalculateVirusComputer(graph, n) << std::endl;
return 0;
}