POJ 2524 유비 쿼터 스 종교 조사

모음 집: (union - find sets)
간단 한 용도 가 광범 위 한 집합 이다. 그리고 집합 은 몇 개의 교차 하지 않 는 집합 으로 비교적 빠 른 합병 과 요소 가 있 는 집합 을 판단 하 는 조작 을 실현 할 수 있 고 응용 이 매우 많다. 예 를 들 어 그림 에 없 는 연결 분량 의 개수 등 이다.가장 완벽 한 응용 은 바로 Kruskar 알고리즘 을 실현 하여 최소 생 성 트 리 를 구 하 는 것 입 니 다.
http://poj.org/problem?id=2524

import java.util.Scanner;

public class Main
{
Scanner scan=new Scanner(System.in);
int[] p=new int[50010];
int num;//      


int find(int x)
{ 
if(p[x]!=x)
p[x]=find(p[x]);
return p[x];
}

//  ，       
void merge(int a,int b)
{
int fa=find(a);
int fb=find(b);
if(fa==fb)
return;
p[fa]=fb;
num--;
}

//   
void init(int n)
{
for(int i=1;i<=n;i++)
{
p[i]=i;
}
num=n;
}
void run()
{
int j=0;
while(true)
{
int n=scan.nextInt();
int m=scan.nextInt();
j++;
if(n==0)
break;
init(n);

for(int i=1;i<=m;i++)
//while(m-->0)
{
merge(scan.nextInt(),scan.nextInt());
}
System.out.println("Case "+j+":"+" "+num);
}
}
public static void main(String[] args)
{
new Main().run();
}
}

고전 조작
그리고 수집 한 정수 (즉, 그의 세 가지 조작 은 코드 템 플 릿 과 결합 하여 이해 합 니 다):
1、Make_Set (x) 모든 요 소 를 하나의 집합 으로 초기 화 합 니 다.
초기 화 된 후에 모든 요소 의 아버지 노드 는 그 자체 이 고 모든 요소 의 조상 노드 도 그 자체 이다 (상황 에 따라 변 할 수도 있다).
2、Find_Set (x) 요소 가 있 는 집합 찾기
원소 가 있 는 집합 을 찾 습 니 다. 그 정 수 는 이 원소 가 있 는 집합 을 찾 은 조상 입 니 다!이것 이 야 말로 판단 과 합병 의 최종 근 거 를 수집 하 는 것 이다.
두 원소 가 같은 집합 에 속 하 는 지 아 닌 지 를 판단 하고 그들 이 모인 조상 이 같은 지 를 보면 된다.
두 집합 을 합 친 것 도 한 집합 조상 을 다른 집합 의 조상 으로 만 드 는 것 이다. 구체 적 으로 는 설명도 가 보인다.
3. Union (x, y) 합병 x, y 가 있 는 두 개의 집합
두 개의 교차 하지 않 는 집합 을 합병 하 는 것 은 매우 간단 하 다.
Find 이용셋 은 두 집합 조상 을 찾 아 한 집합 조상 을 다른 집합 조상 에 게 가 리 켰 다.그림 과 같다
병렬 집합 최적화
1、Find_설정 (x) 시 경로 압축
조상 을 찾 을 때 우 리 는 일반적으로 재 귀적 으로 찾 지만 요소 가 많 거나 나무 전체 가 하나의 사슬 로 변 할 때 매번 FindSet (x) 는 모두 O (n) 의 복잡 도 입 니 다. 이 복잡 도 를 줄 일 방법 이 있 습 니까?
답 은 긍정 적 이다. 이것 이 바로 경로 압축 이다. 즉, 우리 가 '전달' 을 통 해 조상 노드 를 찾 은 후에 '역 추적' 을 할 때 그의 자손 노드 를 조상 에 게 직접 가리 키 는 것 이다. 그러면 나중에 다시 FindSet (x) 시 복잡 도 는 O (1) 가 됩 니 다. 다음 그림 과 같 습 니 다.이 를 통 해 알 수 있 듯 이 경로 압축 은 이후 의 찾기 에 편리 하 다.
2. 유 니 온 (x, y) 시 순서대로 합병
즉, 합 칠 때 요소 가 적은 집합 을 요소 가 많은 집합 에 합 쳐 합 친 후에 나무의 높이 가 상대 적 으로 작 을 것 이다.