글 읽기 - Union-Find 반례 부탁드립니다.

rkdalstjd9 4년 전 0

다른 부분은 문제없고 40~44번째 줄에 대한 질문입니다.

주석 친 부분은 구글링해서 참고한 정답이고 현재 코드는 제 코드 입니다.

34,35 번째 줄에서 1이 무조건 root 에 오게 설정을 해주었습니다.

계속 틀렸습니다가 나오는데 반례를 못찻겠어서 질문 드립니다!

#include <iostream>

using namespace std;

int parent[100];

int Find(int a){
    if (a==parent[a])
        return a;
    int b = Find(parent[a]);
    parent[a] = b;
    return b;
}

void Union(int a,int b){
    a = Find(a);
    b = Find(b);
    if (a!=b)
        parent[b] = a;
}

int main(int argc, const char * argv[]) {
    int N,M;
    
    cin >> N >> M;
    
    for (int i=1;i<=N;i++){
        parent[i] = i;
    }
    
    for (int i=0;i<M;i++){
        int a,b;
        cin >> a >> b;
        if (a>b) Union(b,a);
        else Union(a,b);
    }
    
    int count = 0;
    
    for (int i=2;i<=N;i++){
        //if (Find(1) == Find(i)) count++;
        int root = Find(i);
        if (root == 1) count++;
    }
    
    cout << count << "\n";
    
    return 0;
}

yonsweng 4년 전 0

input

1 3

2 3

이렇게 넣으면

parent[1] = 2

parent[2] = 2

parent[3] = 1

이 되어, 이 코드는 정답인 3이 아니라, 1을 출력하게 됩니다.

yonsweng 4년 전 0

위의 제가 든 예시의 출력이 0이 될 거 같네요.

lekonell 4년 전 3

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 문제였군요... 반례를 잘못 입력해서 삭제했습니다.

yonsweng님의 반례에서 올바른 정답은 2입니다. 1로 인해 2와 3이 감염되기 때문입니다.

park780172 4년 전 0

올려주신 코드는 Union 함수에서

a와 b가 다를 때, b의 부모를 a로 '무조건' 지정하고 있습니다.

따라서, a와 b 중 누가 더 작은지 판단해야 합니다.

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

문제

문제

출처

ICPC

Union-Find 반례 부탁드립니다.

rkdalstjd9 4년 전 0

yonsweng 4년 전 0

yonsweng 4년 전 0

lekonell 4년 전 3

park780172 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말