글 읽기 - 2606번 어느 부분에서 틀린지 궁금합니다.

gazebo1 3년 전 0

Union Find 알고리즘을 참조해서 두 컴퓨터를 연결할 때 두 부모 중에서 항상 더 작은 쪽으로 설정하는 알고리즘으로 작성했는데, 어느 부분에서 틀린 건지 모르겠네요...

#include <iostream>
using namespace std;

int parent[101];

void setParent(int u, int v) {
    int temp = min(parent[u], parent[v]);
    parent[u] = parent[v] = temp;
}

int getParent(int u) {
    if (u == parent[u]) return u;
    return getParent(parent[u]);
}

int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }
    for (int m = 0; m < M; m++) {
        int u, v;
        cin >> u >> v;
        setParent(u, v);
    }
    int count = 0;
    for (int i = 2; i <= N; i++) {
        if (getParent(i) == 1) count++;
    }
    cout << count << '\n';
}

gisung2215 3년 전 0

우왕 저랑 똑같이 짜셨네요ㅎㅎ 저도 틀렸어요 혹시 반례 찾으셨나요?

gazebo1 3년 전 1

간단한 반례입니다.

4 3
1 2
3 4
2 4
output : 2
answer : 3

위 코드에서는 parent[u], parent[v] 중 최솟값을 찾는 것이 문제였습니다. parent배열 값의 최소가 아니라 getParent 함수로 가져온 u와 v 의 부모들 중, 더 큰 값의 parent를 더 작은 값으로 설정해주니 AC 받았습니다.

gisung2215 3년 전 0

감사합니다. 도움이 됐습니다. 좋은 하루 보내세요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2606번 어느 부분에서 틀린지 궁금합니다.

gazebo1 3년 전 0

gisung2215 3년 전 0

gazebo1 3년 전 1

gisung2215 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말