# 1627. Graph Connectivity With Threshold
###### tags: `Leetcode` `Hard` `Union Find`
Link: https://leetcode.com/problems/graph-connectivity-with-threshold/
## 思路
union find 把有相同factor的数group到一起
这里要注意的是因为例如15可能出现在两个group里(有3的和有5的)
但是之前处理的情况是每一个element只会出现在一个group里
所以这里的处理方式是每次都把数值大的当作father
这样3和5都能找到15 但是3找不到5
## Code

class Solution {
    int[] fa;
    public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
        fa = new int[n+1];
        for(int i=0; i<=n; i++){
            fa[i] = i;
        }
        for(int i=threshold+1; 2*i<=n; i++){
            for(int j=i; j<=n; j+=i){
                combine(i,j);
            }
        }
        
        List<Boolean> ans = new ArrayList<>();
        for(int[] query:queries){
            ans.add(find(query[0])==find(query[1]));
        }
        return ans;
    }
    private int find(int a){
        if(fa[a]==a) return a;
        else return fa[a]=find(fa[a]);
    }
    private void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return;
        if(a<b) fa[a]=b;
        else fa[b]=a;
    }
}