[템 플 릿 수집] 낙 곡 P3367

집합 정의
그리고 집합 은 트 리 형 데이터 구조 로 교차 하지 않 는 집합 (Disjoint Sets) 의 합병 과 조회 문 제 를 처리 하 는 데 사용 된다.항상 사용 중 에 숲 으로 표시 한다.집합 은 모든 요소 가 하나의 단일 요 소 를 구성 하 는 집합 이다. 즉, 일정한 순서에 따라 같은 그룹 에 속 하 는 요소 가 있 는 집합 을 합병 하 는 것 이다.
주요 조작
초기 화: 각 점 이 있 는 집합 을 자신 으로 초기 화 합 니 다.일반적으로 이 절 차 는 이 데이터 구 조 를 사용 할 때마다 한 번 만 실행 되 고 어떤 실현 방식 이 든 시간 복잡 도 는 O (N) 이다.찾기: 요소 가 있 는 집합, 즉 루트 노드 를 찾 습 니 다.합병: 두 요소 가 있 는 집합 을 하나의 집합 으로 합 친다.일반적으로 합병 하기 전에 두 요소 가 같은 집합 에 속 하 는 지 판단 해 야 한다. 이것 은 위의 '찾기' 작업 으로 이 루어 질 수 있다.
코드 템 플 릿

#include
using namespace std;
int n,m,k,p,ans=0,pd[500001];
int f[500001],x,y,z;
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=2*n;++i)f[i]=i;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&z,&x,&y);
        int xx=find(x);
        int yy=find(y);
        if(z==1){   
            if(xx==yy)continue;
            f[yy]=xx;
        }
        else{
            if(xx==yy)printf("Y
");
            else printf("N
");
        }

    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

트 리 체인 분할 템 플 릿 (점 권 기반, 변 권 기반)

나무 사슬 의 분할 은 점 권 을 바탕 으로 하고 변 권 을 바탕 으로 점 권 (hdu 3966) 을 바탕 으로 나무 에 있 는 점 에 다시 번 호 를 매 긴 다. p [u] 는 u 가 대응 하 는 위 치 는 변 권...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[템 플 릿 수집] 낙 곡 P3367

좋은 웹페이지 즐겨찾기