백준 2606 - 바이러스

DFS로 풀었음

시작이 1번 정점이어서 DFS(1)을 한 후 연결된 정점이 있을 때마다 cnt++을 해줬음

cnt 값이 정답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <queue>

using namespace std;

bool arr[101][101] = { false }; //연결되었는지 확인하는 배열
bool dfsVisited[101] = { false }; //dfs와 bfs에서 사용할 정점 방문 여부 배열


int N, M;
int cnt = 0;

void DFS(int v) { //시작할 위치, 함수 내에서 출력함
    dfsVisited[v] = true;

    for (int i = 1; i <= N; i++) {
        if (arr[v][i] && !dfsVisited[i]) { //현재 정점과 연결되어 있고 방문한 적 없다면
            DFS(i);
            cnt++;
        }
    }

}



int main() {

    int i;
    int u, v;
    
    scanf("%d %d", &N, &M);


    for (i = 0; i < M; i++) { //정점 입력받기
        scanf("%d %d", &u, &v);
        arr[u][v] = true;
        arr[v][u] = true;
    }

    DFS(1);

    printf("%d", cnt);

    return 0;
}