# 2492. Minimum Score of a Path Between Two Cities
###### tags: `Leetcode` `Medium` `Union Find`
Link: https://leetcode.com/problems/minimum-score-of-a-path-between-two-cities/
## 思路
union find每个group是所有connected的点
记录每个group最小的road weight
答案就是node n所在的group的最小road weight
## Code

class Solution {
    int[] fa;
    int[] min;
    public int minScore(int n, int[][] roads) {
        fa = new int[n+1];
        min = new int[n+1];
        for(int i=0; i<=n; i++){
            fa[i] = i;
            min[i] = Integer.MAX_VALUE;
        }
        for(int[] road:roads){
            combine(road[0], road[1], road[2]);
        }
        return min[find(n)];
    }
    private int find(int a){
        if(fa[a]==a) return a;
        return fa[a] = find(fa[a]);
    }
    private void combine(int a, int b, int dis){
        a = find(a);
        b = find(b);
        fa[b] = a;
        min[a] = Math.min(dis, Math.min(min[a], min[b]));
    }
}