# 2316. Count Unreachable Pairs of Nodes in an Undirected Graph
###### tags: `Leetcode` `Medium` `Union Find`
Link: https://leetcode.com/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/description/
## 思路
union find
unreadable pairs = sum of (每一个group的size * n-这个group的size) / 2
除以2是因为有重复的pair
每个pair都计算了两遍
## Code

class Solution {
    int[] fa;
    int[] size;
    boolean[] visited;
    public long countPairs(int n, int[][] edges) {
        fa = new int[n];
        size = new int[n];
        visited = new boolean[n];
        for(int i=0; i<n; i++){
            fa[i] = i;
            size[i] = 1;
        }
        for(int[] edge:edges){
            combine(edge[0], edge[1]);
        }
        
        long ans = 0;
        for(int i=0; i<n; i++){
            int f = find(i);
            if(visited[f]) continue;
            visited[f] = true;
            ans += (long)size[f]*(n-size[f]);
        }
        return ans/2;
    }
    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;
        size[a] += size[b];
    }
}