连通网络的操作次数-并查集
今天学了点并查集，好像貌似有点搞懂了，当然只是停留在能把代码敲出来。
Union-Find算法详解 - labuladong的算法小抄 (gitbook.io)
这位博主讲的真是好，他画的图很形象，容易理解，解决了把我困扰了好久的并查集。
1319. 连通网络的操作次数
难度：中等
用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。
网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。
给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1
题解
先把并查集模板敲出来：
class UF {
private:
int *parent;
int count;
int *size;
public:
UF(int n) {
this->count = n; // 连通分量
this->parent = new int[n];
this->size = new int[n];
for (int i = 0; i < n; i++) {
this->parent[i] = i;
this->size[i] = 1;
}
}
int Find(int x) {
while (x != parent[x]) {
x = parent[x];
parent[x] = parent[parent[x]];
}
return x;
}
void Union(int a, int b) {
const int x = Find(a);
const int y = Find(b);
if (x == y) return;
if (size[x] > size[y]) {
parent[y] = x;
size[x] += size[y];
} else {
parent[x] = y;
size[y] = size[x];
}
count--;
}
bool Connected(int a, int b) {
return Find(a) == Find(b);
}
int getCount() const {
return count;
}
};
count：连通分量，可以理解成有多少堆元素。
题目：
class Solution {
public:
int makeConnected(int n, vector<vector<int>> &connections) {
const int N = connections.size();
const auto u = new UF(n);
int rest = 0; // 记录多余的线
for (int i = 0; i < N; ++i) {
const int a = connections[i][0], b = connections[i][1];
if (u->Connected(a, b)) {
// 运行到此如果有已经连接的节点，说明该连接多余，可以留着这条线，记录到rest
rest++;
} else {
// 正常就将两台计算机连起来
u->Union(a, b);
}
}
// 最后的结果：剩余的线可以将所有区域（块）的计算机连接起来
return rest >= u->getCount() - 1 ? u->getCount() - 1 : -1;
}
};
思路：将每个计算机连起来，连到某个点发现两台计算机已经连接上了，那就可以省下这条线，跑完之后看剩下有几堆计算机，将多余的线用来连剩余的。
如果剩余的线不够连接这几堆计算机，则不可连接返回-1，否则返回剩下的堆-1
乍眼看还很简单，有这个想法倒是挺难的。
并查集好优雅！
谢谢鱼老师的视频：