무브

오르비

아톰

내 태그

내 태그 설정

입시
학습
생활
클럽
직업·취업
Epioptimus
Centurion

수능쎈츄 [1174003] · MS 2022 · 쪽지

2023-01-01 23:42:28
조회수 2,198

백준 1717번: 집합의 표현(골드 IV)

게시글 주소: https://orbi.kr/00060992012

귀찮아서 문제는 생략

대충 유니온 파인드(Union-Find)를 구현하라는 문제입니다.

근데 이제 경로 압축(weighted-union heuristic)을 하지 않으면 시간 초과로 터집니다 낄낄


제가 아직 전공생이 아니라서 영문명이 맞나 모르겠네요


아무튼 


#include <stdio.h>


int parent[1000001];


int main()

{

    int i,n,m;

    int Do,a,b;

    

    scanf("%d%d",&n,&m);

    

    for(i=0; i<n+1; i++)

        parent[i] = i;

    

    for(i=0; i<m; i++)

    {

        scanf("%d %d%d",&Do,&a,&b);

        

        if(Do)

            printf("%s\n", find(a)-find(b)?"NO":"YES");

        

        else

            merg(a,b);

    }

}


int find(int x)

{

    if (parent[x] == x) return x;

    return parent[x] = find(parent[x]);

}


void merg(int x, int y)

{

    x = find(x);

    y = find(y);

    if (x>y)

        parent[y] = x;

    else

        parent[x] = y;

}



+숏코딩 랭킹을 보면, find함수와 merg함수를 이렇게 축약할 수도 있습니다


f(a){return v[a]-a?v[a]=f(v[a]):a;}

u(a,b){v[f(a)]=f(b);}

0 XDK (+0)

  1. 유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.

수능쎈츄 [1174003]

쪽지 보내기

글쓰기
오르비 1381389번째 회원 가입
ddna
1,422,072 건의 게시물이
블록체인에 디지털 공증되었습니다.
901,751
497,321
22,267
574
159

오늘의 추천 글

2026 수능D - 265

오르비 플레이
오르비 RARE
오르비 과외시장
Move
our corporate site
Orbi Class
on-line classes
Atom
educational books & resources
Gae9
humor and fun

© 2000-2025 Move Inc.

orbisoptimus (v17-704e1f)