#include <iostream>
#include <queue>
using namespace std;

typedef struct Grape { //간선
    int start;
    int end;
} Grape;

bool allVisited(bool* visited, int N); // 모두 방문했는지 확인하는 함수
void bfs(int start, Grape* grapeList, bool* visited, int grapeSize);

int main() {
    int N, M, cnt = 0; // N은 정점 개수 M은 간선 개수 cnt는 연결요소 개수 세주는 놈
    cin >> N >> M;
    Grape grapeList[2 * M]; // 양방향 그래프 저장해줌
    bool visited[N + 1] = {0, };
    for (int i = 0; i < M; i++) { // 그래프 입력받아서 두방향 각각 저장
        int a, b;
        cin >> a >> b;
        grapeList[2 * i].start = a;
        grapeList[2 * i].end = b;
        grapeList[2 * i + 1].start = b;
        grapeList[2 * i + 1].end = a;
    }
    visited[0] = true;
    while (!allVisited(visited, N)) { //모두 방문하기 전까지
        for (int i = 1; i <= N; i++) { //1부터 bfs돌리기
            if (!visited[i]) { //아직 bfs에서 안 돌아가서 연결 안된 애만
                bfs(i, grapeList, visited, 2 * M);
                cnt++;
            }
        }
    }
    cout << cnt;
    return EXIT_SUCCESS;
}

bool allVisited(bool* visited, int N) {
    for (int i = 1; i < N + 1; i++) {
        if (!visited[i]) return false;
    }
    return true;
}

void bfs(int start, Grape* grapeList, bool* visited, int grapeSize) {
    queue <int>q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int cur_start = q.front();
        q.pop();
        for (int i = 0; i < grapeSize; i++) {
            if (grapeList[i].start == cur_start) {
                if (!visited[grapeList[i].end]) {
                    q.push(grapeList[i].end);
                    visited[grapeList[i].end] = true;
                }
            }
        }
    }
}


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

Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net


78%에서 틀림


나는 이제 뭐

6 5 1 2 2 5 5 1 3 4 4 6

이런 입력 오면 

정점 6 간선 5

1부터 검사해서

1 2

1 5가 if문 걸려가지고

2, 5가 큐에 들어가고

2, 5는 다돌려도 따로 만드는놈없으니까

1, 2, 5만 방문됨

cnt++;되고나서

bfs로 다시 3 살펴보고

3 4가 걸려서

4가 큐에 들어가고

4 6 걸려서 6 큐에 들어가고

6 visited되고 큐 비어서 bfs끝나겠지?


이런 문젠데 특이케이스

1 0 

-> 1

2 1

1 2

-> 1

이런 케이스는 잘됨

도와줘!!