# 1135. Connecting Cities With Minimum Cost
###### tags: `Leetcode` `Medium` `Union Find` `Minimum Spanning Tree`
Link: https://leetcode.com/problems/connecting-cities-with-minimum-cost/
## 思路
Minimum Spanning Tree [讲解](https://cloud.tencent.com/developer/article/1424759)
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that **connects all the vertices together**, without any cycles and with the **minimum possible total edge weight.** That is, it is a spanning tree whose sum of edge weights is as small as possible.
## Code

class Solution:
    def minimumCost(self, n: int, connections: List[List[int]]) -> int:
        fa = [i for i in range(n+1)]
        groupCnt = n
        
        def find(a):
            if fa[a] == a: return a
            else: 
                fa[a] = find(fa[a]) 
                return fa[a]

        def inSameGroup(a, b):
            a = find(a)
            b = find(b)
            return a==b

        def combine(a, b):
            a = find(a)
            b = find(b)
            if a==b: return
            fa[a] = b

        connections = sorted(connections, key=lambda c:c[2])
        totCost = 0
        for x, y, c in connections:
            if not inSameGroup(x,y):
                totCost += c
                combine(x, y)
                groupCnt -= 1
        
        return totCost if groupCnt == 1 else -1

class Solution {
    int[] fa;
    int group;
    public int minimumCost(int n, int[][] connections) {
        fa = new int[n+1];
        for(int i=0; i<n+1; i++){
            fa[i] = i;
        }
        Arrays.sort(connections, (a,b)->(a[2]-b[2]));
        group = n;
        int ans = 0;
        for(int[] c:connections){
            if(isSameGroup(c[0],c[1])) continue;
            combine(c[0], c[1]);
            group--;
            ans+=c[2];
        }
        if(group!=1) return -1;
        return ans;
    }
    private int find(int a){
        if(fa[a]==a) return a;
        return fa[a]=find(fa[a]);
    }
    private void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return;
        fa[b]=a;
    }
    private boolean isSameGroup(int a, int b){
        a = find(a);
        b = find(b);
        return a==b;
    }
}