알고리즘 서론 제2 1 장 교차 집합 하지 않 는 데이터 구조 에 사용 된다.

교차 하지 않 는 집합의 정의 와 조작
    교차 하지 않 고 집합 하 는 데이터 구 조 는 하나의 동적 집합 을 유지 하고 모든 집합 은 보통 하나의 대표 (이 집합 하 는 구성원) 가 있 으 며 이 집합 을 표시 한다.분명히 이 동적 집합 은 서로 교차 하지 않 기 때문에 집합 대표 (표지) 도 자연히 유일무이한 것 이다.교차 하지 않 는 집합 에 대해 우 리 는 다음 과 같은 조작 을 지원 할 수 있 기 를 바란다.
    1. MAKE - SET (x): 하나의 집합 을 만 들 고 하나의 요소 x 만 포함 하면 이 집합의 대 표 는 자연히 x 이다.
    2. FIND - SET (x): 요소 x 가 있 는 집합, 즉 이 집합 표지 (대표) 를 되 돌려 줍 니 다.
    3. UNION (x, y): x 와 y 가 각각 속 한 집합 을 합병 하고 합 친 집합 은 x (또는 y) 가 속 한 집합의 대표 이다.
교차 하지 않 는 집합 링크 표시
    이것 은 토론 하지 않 고 비교적 간단 하 다.
연습 문제
   2|E|，|V| - k
연습 문제
   시간 O (n), UNION 작업 은 매번 길이 가 1 인 링크 를 긴 링크 에 연결 하고 포인터 수정 시간 은 모두 O (1) 이다.
연습 문제
   단일 링크 를 돌 이 켜 보 세 요.우 리 는 비교적 짧 은 집합 체인 체인 을 비교적 긴 집합 체인 표 의 머리 결점 의 다음 위치, 즉 머리 삽입 법 이 라 고 할 수 있다.
교차 하지 않 고 숲 을 모으다.
    우 리 는 직접 소스 코드 를 주 었 는데, 알고리즘 이 비교적 간단 해서 말 하지 않 겠 다.순위 에 따라 (이 순 서 는 노드 높이 의 상 계 를 말 하 며 노드 수량 이 아 닙 니 다) 합병 과 경로 압축 을 사 용 했 습 니 다.

#include
#include

using namespace std;

class UFS
{//   1  
private:
	vector parent;
	vector rank;
public:
	explicit UFS(size_t size) :parent(size + 1), rank(size + 1){}
	void makeSet(size_t i)
	{
		parent[i] = i;
		rank[i] = 0;
	}
	void Union(size_t x, size_t y)
	{
		size_t left = findSet(x), right = findSet(y);
		if (rank[left] < rank[right])
			parent[left] = right;
		else
		{
			parent[right] = left;
			if (rank[left] == rank[right])
				++rank[left];
		}
	}
	size_t findSet(size_t x)
	{
		if (x == parent[x]) return x;
		parent[x] = findSet(parent[x]);
		return parent[x];
	}
};

연습 문제

size_t findSet(size_t x)
	{
		size_t p = x;
		while (p != parent[p])
			p = parent[p];
		while (x != p)
		{
			size_t y = parent[x];
			parent[x] = p;
			x = y;
		}
		return parent[x];
	}

연습 문제
    1. n. 이 MAKE - SET 를 먼저 진행 하고 n 개의 요소 만 있 는 집합 을 만 듭 니 다.
    2. n - 1 번 의 UNION 작업 을 진행 하면 나무 한 그루 를 얻 을 수 있 습 니 다. 순서대로 합 쳐 지기 때문에 이 나무의 높이 는 O (lgn) 이 고 상기 두 걸음 의 시간 은 O (n) 입 니 다.
    3. 마지막 으로 m - 2n + 1 번 의 FIND - SET 작업 을 진행 합 니 다. 매번 의 시간 은 O (lgn) 이 고 조작 이 충분 하 다 고 가정 합 니 다. 적어도 m > = 3n 이 라면 적어도 n - 1 번 의 FIND - SET 작업 이 있어 야 합 니 다. 그리고 n < = m / 3 이 므 로 작업 총 시간 은 O (mlgn) 입 니 다.
연습 문제
    기장 방법 을 채택 하면 얻 을 수 있 는 시간 은 O (m) 이다.
    1. 모든 MAKE - SET 작업 에 2 위안 의 보 수 를 부여 하고 1 위안 은 집합 을 만 드 는 비용 을 지불 하 며 다른 1 위안 은 저금 하고 나중에 사용한다.
    2. 모든 LINK 작업 에 1 원 의 보 수 를 부여 하고 해당 작업 의 대 가 를 지불 하 는 데 사용 합 니 다.
    3. 똑 같이 모든 FIND - SET 작업 에 대해 우 리 는 1 원 만 지불 합 니 다.만약 에 경로 압축 만 사용 하면 재 귀적 호출 에서 모든 노드 에 대해 최대 한 번 은 parent 를 재 설정 할 수 있 습 니 다. 이때 우 리 는 이전에 저금 한 1 원 으로 대 가 를 지불 하면 충분 합 니 다.
   모든 조작의 대가 가 최대 2 이기 때문에 m 개의 조작 서열 은 가장 많은 총 대가 가 2m 이기 때문에 총 시간 은 O (m) 이다.또한 상기 분석 에서 우 리 는 경로 압축 만 사 용 했 을 뿐 순위 에 따라 합병 하지 않 았 다.
사고 문제 21 - 1
   (a) E1 ~ E6 는 각각 4, 3, 2, 6, 8, 1 이다.
   (b) 순환 불변 식: i 차 교체, 즉 숫자 i, 앞의 1, 2... i - 1 은 모두 처 한 집합 j 를 찾 았 고 j 가 되 었 다.
    초기: i 는 1 이 고 앞 에 숫자 가 없 으 며 성립 됩 니 다.
    유지: 숫자 i 가 집합 j 에 있 는 지 확인 하고 알고리즘 3 ~ 6 줄, 만약 j
    종료: i = n + 1. 순환 불변 식 에 따라 알 수 있 습 니 다. i 이전, 즉 1 ~ n 은 모두 소속 집합 j (m + 1 일 수 있 음) 를 찾 았 고 extracted (m + 1 일 때 제외) 를 정확하게 설정 하여 이 알고리즘 이 정확 하 다 는 것 을 증명 합 니 다.
    (c) 모든 insert 집합 에 대해 하나의 체인 체인 으로 연결 하고 j 를 집합 하면 삭제 합 니 다.
      1. i 가 어느 집합 에 속 하 는 지 확인 하고 FIND - SET 를 사용한다.
      2. 다음 사용 가능 한 집합 을 얻 고 링크 의 next 도 메 인 을 사용 합 니 다.
      3. 합병 은 UNION 을 사용 합 니 다.
    이전 에는 MAKE - SET 가 n 회, UNION 이 n - 1 회, 순환 에 따라 n 회 FIND - SET 가 있 었 다 면 시간 은 분명히 O (na (n) 였 다.
사고 문제 21 - 3 Tarjan 의 오프라인 최소 공공 조상 알고리즘