응용 총 결 을 수집 하 다.

일. 병 집 된 개념
그리고 집합 은 일종 의 알고리즘 으로 상호 관련 (같은 집합 에 속 함) 요 소 를 몇 개의 집합 에 속 하 는 지 판단 할 수 있 고 그림 구조 중의 두 점 이 연결 되 어 있 는 지 판단 할 수 있다.그리고 집합 한 디자인 방향 은 다음 과 같다.
프로그램 실행 과정 에서 임 의 요 소 는 반드시 다음 과 같은 세 가지 상태 에 져 야 한다.
1. 즉, f [i] = i. 이 상태 에서 요 소 는 합병 되 지 않 았 을 수도 있 고 합병 을 거 쳤 을 수도 있 지만 선택 한 부모 노드 가 바로 이 노드 입 니 다.
2. 부모 노드 가 있 고 현재 상태 에서 진정한 부모 노드 (사실은 가장 정상 적 인 상태 이 고 두 번 째 상태 도 첫 번 째 상황 을 포함한다).
3. 부모 노드 가 있 지만 현재 상태 에서 진정한 부모 노드 가 아니다. 예전 의 부모 노드 일 수도 있다. merge 함수 에서 알 수 있 듯 이 두 노드 를 합병 할 때 두 노드 의 부모 노드 만 합병 할 뿐이다. 이 노드 의 부모 노드 가 자체 가 아 닐 때 이 노드 의 부모 노드 는 새로운 부모 노드 로 바 뀌 지 않 는 다. 이런 상 태 는 집합 수량 을 통계 할 때 위험 하 다.회 로 인해 집합 수량 이 증가 하지만 이 문 제 를 걱정 하지 않 아 도 됩 니 다. getf 함수 (부모 노드 찾기) 를 자세히 살 펴 보면 f [a] = getf (f [a]) 라 는 코드 를 발견 할 수 있 습 니 다. 원래 getf 함 수 는 각 노드 의 아버지 뿐만 아니 라 각 노드 의 f [] 값 도 수정 하여 아버지의 f [] 값 과 일치 하 게 만 들 었 습 니 다.그래서 이 노드 나 이 노드 의 하위 노드 가 merge 에 의 해 다시 합 쳐 질 때마다 이 노드 의 f [] 는 정확 한 값 으로 수정 되 지만 문제 가 발생 합 니 다. 만약 에 이 노드 가 다시 합 쳐 지지 않 으 면 어떻게 합 니까?안전 한 조작 은 merge 가 모든 노드 를 완성 한 후에 getf 이하 의 모든 노드 를 사용 해 야 합 니 다. 그러면 모든 노드 가 정확 합 니 다.
2. 병 집 된 응용
1. 집합 요 소 를 합병 하고 결합 수량 을 확정 하 며 요소 가 어느 집합 에 속 하 는 지 찾 습 니 다.
2. 그림 구조 에서 (그림 속 의 점 은 바로 요소) 두 점 이 연결 상태 에 있 는 지 확인 하고 예 를 들 어:
(1) Kruskal 법 최소 생 성 트 리
사고: 모든 변 을 길이 의 크기 에 따라 정렬 하고 작은 것 부터 큰 것 까지 줄 선택 을 합 니 다. 한 쪽 을 선택 할 때마다 양쪽 의 점 을 사용 하고 집합 을 합 칩 니 다. 만약 에 선택 한 변 경 과 집합 조회 가 연결 되 었 다 면 이 변 을 뛰 어 넘 습 니 다.
문제.
가중치 가 있 는 그림 을 지정 하여 연통 도 안의 모든 노드 의 최소 경 로 를 찾 습 니 다.
데이터
6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
코드

//
//  main.cpp
//          kruskal  
//
//  Created by     on 16/3/18.
//  Copyright ? 2016     . All rights reserved.
//

#include 
#include 
#include 
using namespace std;
int f[50];
struct line
{
    int u;
    int v;
    int w;
}lines[50];
int cmp(const void *a,const void *b)
{
    return (*(line *)a).w>(*(line *)b).w?1:-1;
}
void init(int n)
{
    for(int i=1;i<=n;i++) f[i]=i;
}
int getf(int a)
{
    if(f[a]==a) return a;
    else
    {
        f[a]=getf(f[a]);
        return f[a];
    }
}
int  merge(int a,int b)
{
    int t1,t2;
    t1=getf(a);
    t2=getf(b);
    if(t1!=t2)
    {
        f[t2]=t1;
        return 1;
    }
    else return 0;
}
int main(int argc, const char * argv[]) {
    freopen("/Users/zhangjiatao/Desktop/input.txt","r",stdin);
    int n,m,sum;
    sum=0;
    cin>>n>>m;
    init(n);
    for(int i=0;i<=m-1;i++)
    {
        cin>>lines[i].u>>lines[i].v>>lines[i].w;
    }
    qsort(lines,m,sizeof(lines[0]),cmp);
    for(int i=0;i<=m-1;i++) cout<

 
3. 집합 템 플 릿
1. 문제
m 조 n 개 원소 간 의 관 계 를 정 하고 이 원소 들 은 집합 에 속 하 는 지 물 어보 십시오
2. 입력

#include 
#include 
using namespace std;
int f[50];
void init(int n)
{
    for(int i=1;i<=n;i++) f[i]=i;
}
int getf(int a)
{
    if(f[a]==a) return a;
    else
    {
        f[a]=getf(f[a]);
        return f[a];
    }
}
void merge(int a,int b)
{
    int t1,t2;
    t1=getf(a);
    t2=getf(b);
    if(t1!=t2)
    {
        f[t2]=t1;
    }
}
void print(int n)
{
    for(int i=1;i<=n;i++) cout<>n>>m;
    init(n);
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        merge(a,b);
        print(n);
    }
    for(int i=1;i<=n;i++)
    {
    	f[i]=getf(i);
	}
    for(int i=1;i<=n;i++)
        if(f[i]==i) sum++;
    cout<

10 8
1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
2 4