原题链接:

https://leetcode.cn/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/description/

解法1: 并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

typedef long long LL; 

class Solution {
public:
    vector<int>p;
    // 并查集的根 及其 集合内对应点的数量
    unordered_map<int,int>cnt;

    int find(int x){
        if(x!=p[x]){
            p[x] = find(p[x]);
        }
        return p[x];
    }

    // 合并 
    void merge(int x,int y){
        int a = find(x);
        int b = find(y);


        // 无向边采用这种方式 对点进行合并 防止重复 但同时又能确保所有点都合并
        if(a <= b){
            p[a] = b;
        }else{
            p[b] = a;
        }

    }

    long long countPairs(int n, vector<vector<int>>& edges) {
        p.resize(n);

        // 并查集初始化
        for(int i = 0; i < n ; i++){
            p[i] = i;
        }

        for(auto e: edges){
            merge(e[0],e[1]);
        }

        for(int i = 0 ; i < n ; i++){
            int root = find(i);
            cnt[root] = cnt[root] + 1;
        }

        LL ans = 0;


        /*
            v个点自成一个集合 那么一共有n个点
            那么这个v个点自然与 n - v 个点不能相互抵达
        */
        for(auto [k,v] : cnt){
            ans += 1L * (n - v) * v;
        }

        return ans/2;
    }
};

解法2: DFS