---
tags: 圖論
title: MST & Disjoint Set
---

:::info
#### [ZJ a445](https://zerojudge.tw/ShowProblem?problemid=a445)
#### [TIOJ 1163](https://tioj.ck.tp.edu.tw/problems/1163)
:::

:::success
# 並查集 Disjoint Set

## 用途
- 查詢兩節點是否位於同一連通塊

## 實作
- 用parent陣列記錄每個node的祖先，初始化以自身為祖先

- 優化：union by size(aka啟發式合併)，union by rank(盡量連到同一個parent上)

int size[100001], parent[100001];

void init() {
    for (int i=1; i<100001; i++) {
        size[i] = 1;
        parent[i] = i;
    }
}

int find(int n) {
	int root = n;
	while (parent[root] != root) {
		root = parent[root];
	}
	int temp;
	while (parent[n] != x) {
	       temp = n;
		n = parent[n];
		parent[temp] = root;
	}
	return root;
}

init();
while(cin >> a >> b) {
    pa = find(a);
    pb = find(b);
    if (pa == pb) break;
    if (size[pa] > size[pb]) {
        parent[pb] = pa;
        size[pa] += size[pb];
    }
    else {
        parent[pa] = pb;
        size[pb] += size[pa];
    }
}

:::

:::info
#### [ZJ a129](https://zerojudge.tw/ShowProblem?problemid=a129)
#### [kickstart 2021 round_A pD](https://codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068c2c3)
:::

:::success
# 最小生成樹 Minimum Spanning Tree

## 定義
- Spanning Tree : 用最少邊數連接所有節點

- N個節點 → N-1條邊

- Minimum : 所有Spanning Tree中邊權和最小的其中一棵

## Kruskal演算法
- Greedy想法

- 按邊權由小到大嘗試連接

- 用並查集避免環的產生
:::