글 읽기 - 1717번 질문

ghdwldn0729 2년 전 0

계속 틀렸습니다가 나오는데, 왜 틀렸는지 고민해봐도 찾기가 어렵습니다. 혹시 어느 부분이 틀렸나요? 제가 유니온 파인드 문제를 처음 접해봐서 구현을 잘못한 건가요?

#include <stdio.h>
#define MAXN 1000001
using namespace std;
int parent[MAXN];
int rank[MAXN];

void initialize(int x);
int find(int x);
void isfind(int a, int b);
void uni(int x, int y);
void func(int flag, int a, int b);

int main(void){
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i=0;i<=n;i++){
        initialize(i);
    }
    for(int i=0;i<m;i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        func(a, b, c);
    }
}

void initialize(int x){
    parent[x]=x;
}

int find(int x){
    if(x==parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}

void isfind(int a, int b){
    if(find(a)==find(b))
        printf("YES");
    else
        printf("NO");
}

void uni(int x, int y){
    x=find(x);
    y=find(y);
    parent[find(y)]=find(x);
}

void func(int flag, int a, int b){
    if(flag==0)
        uni(a, b);
    if(flag==1)
        isfind(a, b);
}

ghdwldn0729 2년 전 0

저는 노드를 쭉 연결하는 식으로 생각했어서 코드를 저렇게 짰습니다. 혹시 왜 인덱스를 비교해야 하나요?

circlezer0 2년 전 1

틀렸습니다를 받은 이유는 \n를 안해서였네요

일반적으로는 더 작은 인덱스를 부모 인덱스로 하는데, 질문자님 코드와 같이 짜면 집합에서 어떠한 노드도 부모가 될 수 있기에

디버깅 시 조금 어려움을 겪을 수도 있다는점 말고는 성능에는 문제가 없네요

죄송합니다.

circlezer0 2년 전 0

출력에 \n를 끼워넣으면 AC를 받을 수 있습니다.

ghdwldn0729 2년 전 0

감사합니다!!

가장 기본적인 걸 빠뜨렸네요ㅎㅎㅎ

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

문제

문제

출처

ICPC

1717번 질문

ghdwldn0729 2년 전 0

ghdwldn0729 2년 전 0

circlezer0 2년 전 1

circlezer0 2년 전 0

ghdwldn0729 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말