2606_바이러스

그래프의 첫번째 노드에서 출발해서 연결된 서로 연결된 노드들은 모두 감염된다. 

첫 번째 노드가 속하지 않는 그래프에는 감염되지 않는다. 

그렇다면 첫번째 노드가 속한 그룹의 개수를 세면 감염되는 컴퓨터의 수를 알 수 있게 된다. 

#include <iostream> using namespace std; int arr[105][105]; bool visited[105] = {false, }; int vertex_num, edge_num; int infect_num = -1; void dfs(int startvertex){ visited[startvertex] = true; infect_num++; for (int i = 1; i <= vertex_num; i++){ if (!visited[i] && arr[startvertex][i] == 1){ dfs(i); } } } int main(){ cin >> vertex_num >> edge_num; for (int i = 1; i <= edge_num; i++){ int vertex_x, vertex_y; cin >> vertex_x >> vertex_y; arr[vertex_x][vertex_y] = 1; arr[vertex_y][vertex_x] = 1; } dfs(1); cout << infect_num << endl; return 0; }