【每日一题Day354】LC2316统计无向图中无法互相到达点对数 | 并查集

统计无向图中无法互相到达点对数【LC2316】

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

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

• 思路

  • **并查集查找连通性：**记录每个点的父节点，父节点相同的节点可以相互到达；与父节点不同的节点，不可以互相到达
  • 计算数量，父节点为$i$的节点数量为$a$，那么这个节点与$n-a$个节点不相邻，统计数量
  • 统计结果，由于重复计算，最终结果需要除以2

• 实现

  class Solution {
      public long countPairs(int n, int[][] edges) {
          // 并查集记录每个点的父节点，父节点相同的节点可以相互到达；与父节点不同的节点，不可以互相到达
          // 计算数量，父节点为i的节点数量为a，那么这个节点与n-a个节点不相邻，统计数量
          // 统计结果，由于重复计算，最终结果需要除以2
          UnionFind union = new UnionFind(n);
          for (int[] edge : edges){
              union.union(edge[0], edge[1]);
          }
          long res = 0L;
          for (int i = 0; i < n; i++){
              res += n - union.getSize(i);
          }
          return res / 2;
  
      }
  }
  // 并查集类
  class UnionFind {
      private int[] p;// 父节点
      private int[] size;// 每个节点的子节点个数（包括自身）
  	// 初始化
      public UnionFind(int n) {
          p = new int[n];
          size = new int[n];
          for (int i = 0; i < n; ++i) {
              p[i] = i;
              size[i] = 1;
          }
      }
  	// 找到节点x的根
      public int find(int x) {
          if (p[x] != x) {
              p[x] = find(p[x]);
          }
          return p[x];
      }
  	// 在并查集中加入a->b的根
      public void union(int a, int b) {
          int pa = find(a), pb = find(b);
          if (pa != pb) {
              if (size[pa] > size[pb]) {
                  p[pb] = pa;
                  size[pa] += size[pb];
              } else {
                  p[pa] = pb;
                  size[pb] += size[pa];
              }
          }
      }
      public int getSize(int a){
          int father = find(a);
          return size[father];
      }
  
  }
  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

  • 复杂度分析
    • 时间复杂度：$O(n+\alpha (m)\ast m)$，$n$为图中顶点的数目，$m$为图中边的数目。其中 $\alpha$为阿克曼函数的反函数，其增长极其缓慢，也就是说其单次操作的平均运行时间可以认为是一个很小的常数。
    • 空间复杂度：$O(n)$，空间复杂度主要取决于并查集，并查集需要 $O(n)$的空间，因此总的空间复杂度为$O(n)$。