글 읽기 - Collapsing-Find가 문제인가요?

metadata 7년 전 0

우선 알고리즘을 설명하자면

이 문제의 케이스들을 반대로 돌려 보면 전형적인 Union-Find가 된다는 점에 착안해

정말 반대로 돌렸습니다.

결과는 초반 테스트 케이스에서 TLE이고요,

아직 무한루프 TLE인지 알고리즘 TLE인지 판별을 못 했습니다.

만약 알고리즘 TLE라면 의심가는 부분이 하나 있긴 한데,

Union-Find의 두 가지 요소 중 하나인 Collapsing Find를 구현 방법을 까먹어서

단순히 현재 찾는 노드를 루트에 갖다붙이는 식으로밖에 처리해주지 않았다는 점입니다.

과연 그 부분이 문제인가요? 그렇다면 Collapsing Find를 어떤 방식으로 구현해야 좋을까요?

아니면 다른 부분에서 문제될 만한 부분이 있나요?

///반대로 돌리면 Union-Find가 되는 전설적인 문제
#include<cstdio>
#define MAX 200000

int n,q,par[MAX+1],node[MAX+1][2],qq[MAX+1][3],ans[MAX+1],nans;

int main(){
    scanf("%d %d",&n,&q);
    par[1]=1;
    node[1][0]=1;
    int i,tp,tc;
    for(i=2;i<=n;i++){
        node[i][0]=i;
        scanf("%d",&par[i]);
    }
    for(i=0;i<n+q-1;i++){
        scanf("%d",&qq[i][0]);
        if(!qq[i][0]){
            scanf("%d",&qq[i][1]);
        }else{
            scanf("%d %d",&qq[i][1],&qq[i][2]);
        }
    }
    for(i=n+q-2;i>=0;i--){
        if(!qq[i][0]){
            tc=qq[i][1];
            tp=par[tc];
            while(node[tp][0]!=tp){
                tp=node[tp][0];
            }
            while(node[tc][0]!=tc){
                tc=node[tc][0];
            }
            if(node[tp][1]>node[tc][1]){
                node[tc][0]=tp;
            }else{
                node[tp][0]=tc;
                if(node[tp][1]==node[tc][1]){
                    node[tc][1]++;
                }
            }
        }else{
            tp=qq[i][1];
            tc=qq[i][2];
            while(node[tp][0]!=tp){
                tp=node[tp][0];
            }
            while(node[tc][0]!=tc){
                tc=node[tc][0];
            }
            node[qq[i][1]][0]=tp;
            node[qq[i][2]][0]=tc;
            if(tp==tc){
                ans[nans]=1;
            }else{
                ans[nans]=0;
            }
            nans++;
        }
    }
    for(i=q-1;i>=0;i--){
        if(ans[i]){
            printf("YES\n");
        }else{
            printf("NO\n");
        }
    }
    return 0;
}

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

문제

문제

출처

ICPC

Collapsing-Find가 문제인가요?

metadata 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말