[BOJ] 11724 연결 요소의 개수

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int> > v;
int visit[1001];

void dfs(int idx)
{
    visit[idx] = 1;

    for (int i = 0; i < v[idx].size(); i++) {
        if (visit[v[idx][i]] == 0)
            dfs(v[idx][i]);
    }
}

int main()
{
    int n, m;

    scanf("%d %d", &n, &m);
    v.resize(n + 1);

    int x, y;
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (visit[i] == 0) {
            dfs(i);
            count++;
        }
    }
    printf("%d", count);

    return 0;
}

풀이: 8분
코딩: 15분
디버깅: 15분

 

세 번 틀렸다.
처음엔 노드 번호를 index로 사용하기로 했으면서 (노드 번호-1)로 수행하고 있던 걸 수정했다.
두 번째엔 visit 배열의 크기를 1000에서 1001로 수정했다.
세 번째엔 v[x]에만 y를 push하던 걸 v[y]에도 x를 push하도록 수정했다.

간선 입력이 노드 번호 순서대로 들어온다는 조건은 없다.

따라서 위 그래프에 대한 입력이 다음과 같을 수 있다.
5 4
5 4
2 1
1 3
4 1
이 때 출력은 1이 옳지만 양방향 연결을 하지 않으면 main에서 dfs를 4번 수행하고 count가 4가 된다.