LC1319.连通网络的操作次数

LC1319.连通网络的操作次数
image.png

思路：并查集

  • 并查集模板题
  • 什么时候会无法充分连接？给的线数量太少了，只要线的数量足够多，那么一定可以连接全部的机器。所以，如果connections.size() < n - 1，就不行，否则就足够连接。

  • 逐个连接即可。最后数堆的数量。set_count记录堆的数量，每次连接，则set_count - 1，最后剩下的set_count就是连接的总数量。

    代码：

    ```cpp // 并查集模板 class UnionFind { public: vector fa; vector r; int n;

    // 当前连通分量数目 int set_count;

public: UnionFind(int _n): n(_n),set_count(_n), fa(_n), r(_n, 1) { iota(fa.begin(), fa.end(), 0); }

  1. int find(int x) {
  2.     return fa[x] == x ? x : fa[x] = find(fa[x]);
  3. }
  5. void merge(int x, int y) {
  6.     x = find(x);
  7.     y = find(y);
  8.     if (x != y) {
  9.         if (r[x] <= r[y]) {
  10.             fa[x] = fa[y];
  11.         } else {
  12.             fa[y] = fa[x];
  13.         }
  15.         if (r[x] == r[y]) {
  16.             r[y] += 1;
  17.         }
  19.         set_count -= 1;
  20.     }
  21. }

};

class Solution { public: int makeConnected(int n, vector>& connections) { if (connections.size() < n - 1) { return -1; }

    UnionFind uf(n);
    for (const auto& conn: connections) {
        uf.merge(conn[0], conn[1]);
    }

    // 已经提前判断了，直接返回即可
    return uf.set_count - 1;
}

}; ```