leetcode 统计无向图中无法互相到达点对数

给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。

请你返回 无法互相到达 的不同 点对数目 。

示例 1：

输入：n = 3, edges = [[0,1],[0,2],[1,2]]
输出：0
解释：所有点都能互相到达，意味着没有点对无法互相到达，所以我们返回 0 。

示例 2：

输入：n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
输出：14
解释：总共有 14 个点对互相无法到达：
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]]
所以我们返回 14 。

提示：

• 1 <= n <= 105
• 0 <= edges.length <= 2 * 105
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• 不会有重复边。

C++

class Solution {
public:
    int find(int x) {
        if(pre[x]==x) {
            return x;
        }
        int y=pre[x];
        int root=find(y);
        pre[x]=root;
        return root;
    }
    
    long long countPairs(int n, vector<vector<int>>& edges) {
        pre.resize(n);
        for(int i=0;i<n;i++) {
            pre[i]=i;
        }
        for(auto e:edges) {
            int x=e[0];
            int y=e[1];
            int root1=find(x);
            int root2=find(y);
            if(root1!=root2) {
                pre[root2]=root1;
            }
        }
        unordered_map<int,long> mp;
        for(int i=0;i<n;i++) {
            int root=find(i);
            mp[root]++;
        }
        long res=(long)n*(long)(n-1)/2;
        for(auto it:mp) {
            res-=it.second*(it.second-1)/2;
        }
        return res;
    }
private:
    vector<int> pre;
};