cpp) 백준 2606: 바이러스

Problem

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

 

Solution

  

    
    
    
    
  
#include<iostream>
#include<vector>
#include<stack>

using namespace std;
#define MAX 101

int n;                    // 정점의 수
int m;                    // 간선의 수
bool map[MAX][MAX];       // 네트워크 연결
bool visited[MAX]={0,};   // 정점 방문 여부
int cnt = 0;             // 웜 바이러스에 걸린 컴퓨터 수 = 정답값


void dfs(int x){  // 정점을 인자로 받음
    visited[x]=1;
    cnt++;
    for(int i=1;i<=n;i++){
        if(map[x][i]==1 && visited[i]==0){
            // 현재 정점과 연결돼있고 방문한 적이 없는 경우
            dfs(i);
        }
    }
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    cin >> n;
    cin >> m;
    for(int i=0;i<m;i++){
        int a,b;
        cin >> a >> b;
        map[a][b]=1;
        map[b][a]=1;
    }

    dfs(1);

    cout << cnt-1 << '\n';  // 1번 컴퓨터는 제외
  
    return 0;
}