樹狀圖 (tree)

樹是一種特殊的圖，任意兩個點只存在唯一一條路徑。在樹中可以指定一個節點當根。

在樹狀圖中，也有一些專屬於樹的特別名詞
注意！圖論的名詞也可以適用在樹上面，因為樹也是一種圖。
樹是一個，連通，無向且沒有環的圖。在樹上，任兩個點只能有一個路徑，邊的數量一定會是點的數量 – 1。

• 根 (root)：一個樹的最上面的節點，就像上圖的 A 節點
• 子節點 (child)：一個節點下一層連到他的節點
• 父節點 (father)：節點上一層連到他的節點 （只會有一個）
• 深度 / 高度 (depth / height)：一個樹有幾層節點
• 子樹 (subtree)：原本樹的一小部分
• 祖先 (ancestor)：父親方向到根的所有節點都叫做這個節點的祖先，也就是父節點，父親的父節點，父親的父親的父節點… 都是這個節點的祖先

樹上 dfs / bfs

在樹上，我們可以用上一章學到的 dfs / bfs，但是由於沒有環，我們可以不用開 vis 陣列，只要判斷不要走回父節點即可。

vector <int> G[mxn];
void dfs(int u, int p){ // 當前節點, 父節點
    for(int v : G[u]){
        if(v == p) continue;
        dfs(v, u);
    }
}

並查集 (Disjoint Set Union Find)

我們可以用圖點跟邊的特性來儲存一些資料，用來表示不同 (disjoint) 的集合。並查集中主要有兩種操作：

Union / Merge (合併): 將兩個點合併起來，也就是把一個點加入另一個點的集合當中

Find (查詢): 查詢這個集合中的根 (root) 結點是誰這種資料結構能讓我們很快的處理不同元素是否在同一個集合裡。

在實作上我們可以用點跟邊來記錄連通資料。我們開一個陣列叫做 par[]，儲存每個的父節點是誰，一開始都預設成自己。這樣我們在合併的時候，就只要把第二個集合的根結點的 par 直接設成第一個集合的根結點就可以了。要查詢的話，我們可以順著 par 往上找，直到看到 par[x] == x 的節點就代表找到根了。

const int mxn = 2e5 + 5;
int par[mxn];
void init(){
    for(int i = 0;i < mxn;i++){
        par[i] = i;
    }
}
int find(int x){
    if(par[x] == x) return x;
    return find(par[x]);
}
void merge(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return;
    par[x] = y;
}

聰明的你們可能會發現，雖然這樣合併集合很快，可是找根結點的速度可能會很慢，因為我的資料可能是一條練 (1->2->3->4->5 … )。這樣每次查詢都要從最下面跑道最上面，要花 O(n) 的時間。所以接下來，我會介紹兩種常見的優化方法，啟發式合併和路徑壓縮。

路徑壓縮就是指把一個集合裡面的點，全部直接連接到集合的根，這樣就不需要每次查詢都從最下面跑到最上面。只需要跑一次之後，我們就把所有的點都直接連到根，這樣接下來的查詢都可以變得很快。

啟發式合併則是指在合併兩個集合的時候，用小的合併到大的。也就是 par[x] = y 的時候，x 應該要是元素比較少的集合，y 要是比較大的集合。這樣均攤下來我們每次操作的複雜度會變成 O(logn)。OI Wiki 對於複雜度有比較清楚的解釋，有興趣的同學可以看看。如果啟發式合併以及路徑壓縮一起使用的話，平均複雜度會變為 O(\alpha n)，其中 \alpha 是阿克曼函數的反函數，大小基本跟常數差不多。但是有時候我們會不希望用路徑壓縮，因為路徑壓縮會改變集合裡的結構，像是在之後更進階的 rollback dsu，我們就無法使用路經壓縮。以下就是兩種優化都使用的 dsu 程式碼。

const int mxn = 2e5 + 5;
int par[mxn];
int sz[mxn];
void init(){
    for(int i = 0;i < mxn;i++){
        par[i] = i;
        sz[i] = 1;
    }
}
int find(int x){
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
    // 在遞迴的時候把路徑上的點的 par 直接設成根
}
void merge(int x, int y){
    x = find(x), y = find(y);
    if(x == y) return;
    if(sz[y] < sz[x]) swap(x, y); // 需要多開陣列 sz 記錄集合大小
    par[x] = y;
    sz[y] += sz[x];
}

最小生成樹 (Minimum Spanning Tree, MST)

最小生成樹的問題是: 生成樹就是在一張圖裡面取出一顆樹。給你一張有邊權 (花費) 的圖，你可以選其中的任意條邊，並讓所有的點連起來，變成一個數。你要找到花費最小的那顆生成樹。最小生成樹有兩種常用的解法 Prim 跟 Kruskal 演算法，兩個都是 greedy 的一種演算法，這邊我們著重介紹 Kruskal，對 Prim 有興趣的同學可以到演算法筆記看看。

Kruskal 的想法很簡單，我們把所有的邊按照邊權排序，只要這條邊對生成樹有貢獻，也就是邊所連接的兩個點本來不是連通的，我們就用這條邊。如果這條邊的兩個端點本來就已經連通了，加這條邊就會形成環，那就不要選。這個 greedy 演算法的嚴謹證明比較複雜，有興趣的同學可以去這個網站看看。

不過我們先講回實作的部分。有沒有發現我們會需要很快的判斷兩個點是否在同個集合裡面，並且將兩個點合併起來? 我們可以用 DSU 並查集很快地做到這件事! 這樣的話，我們演算法的複雜度就會是 O(ElogE)，其中 E 是邊的數量，也就是排序所要花費的時間，因為在合併和查找點的複雜度會比 O(ElogE) 來的小。

下面是我拿 Zerojudge a129. 最小生成樹當例題，實作的部分!

#include <bits/stdc++.h>
using namespace std;
const int mxn = 1e5 + 5;
int par[mxn];
int sz[mxn];
void init(){
    for(int i = 0;i < mxn;i++){
        par[i] = i;
        sz[i] = 1;
    }
}
int find(int x){
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
}
void merge(int x, int y){
    x = find(x), y = find(y);
    if(x == y) return;
    if(sz[y] < sz[x]) swap(x, y); 
    par[x] = y;
    sz[y] += sz[x];
}
struct Edge{ 
    int u, v, w; 
};
bool cmp(Edge a, Edge b){
    return a.w < b.w;  
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	while(cin >> n >> m) {
		vector <Edge> vec; 
		init();
	    for(int i = 0;i < m;i++){
	        int a, b, w;
	        cin >> a >> b >> w;
	        vec.push_back({a, b, w});
	    }
	    int cnt = n-1;
	    sort(vec.begin(), vec.end(), cmp);
	    long long ans = 0;
	    for(Edge e : vec){
	        if(find(e.u) != find(e.v)) {
	            merge(e.u, e.v);
	            ans += e.w;
	            cnt --;
	        }
	    }
	    if(cnt != 0) cout << -1 << '\n';
	    else cout << ans << '\n';
	}
}