題目描述

題目分析

ps：這篇博客是補前天的，前天在老家不方便寫博客
題目挺簡單的，但是通過題目對圖的連通性有了一個更深刻的認識：如果有超過（或等于）n-1條邊，則一定是可以讓整個圖聯通的。
如果想讓整個圖聯通，只需要求出整個圖的聯通分量個數，然后-1就是需要的邊的個數（即讓這寫聯通分量聯通即可）

AC代碼

class UnionFind {
public:vector<int> father;vector<int> size;int n;int setCount;UnionFind(int _n):n(_n),setCount(_n),father(_n),size(_n,1) {iota(father.begin(), father.end(), 0);}int root(int x) {return x == father[x] ? x : father[x] = root(father[x]);}bool unite(int x, int y) {x = root(x);y = root(y);if (x == y) {return false;}if (size[x] < size[y]) {swap(x, y);}father[y] = x;size[x] += size[y];--setCount;return true;}bool connected(int x, int y) {return root(x) == root(y);}
};
class Solution {
public:int makeConnected(int n, vector<vector<int>>& connections) {if (connections.size() < n - 1) {return -1;}UnionFind uf(n);for (auto &edge : connections) {uf.unite(edge[0], edge[1]);}return uf.setCount - 1;}
};