【Day 78 】2022-02-27 - 1319. 连通网络的操作次数

[azl397985856]

1319. 连通网络的操作次数

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/

前置知识

暂无

题目描述

用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。

示例 1：

输入：n = 4, connections = [[0,1],[0,2],[1,2]]
输出：1
解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。
示例 2：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
输出：2
示例 3：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
输出：-1
解释：线缆数量不足。
示例 4：

输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
输出：0

提示：

1 <= n <= 10^5
1 <= connections.length <= min(n*(n-1)/2, 10^5)
connections[i].length == 2
0 <= connections[i][0], connections[i][1] < n
connections[i][0] != connections[i][1]
没有重复的连接。
两台计算机不会通过多条线缆连接。

[charlestang]

思路

并查集。

1. n 台电脑，需要 n -1 条线连接。len(connections) 就是电线的数量，设其等于 m。如果 m < n - 1，则不可能，直接返回 -1。
2. 初始状态下，我们假设孤岛一共有 cnt = n 个。然后根据 connections 的连接情况，每连接上一台电脑，孤岛数量减少 1。不难想象，如果所有电脑都能连接，那么孤岛剩余数量正好是 1。这也是我们的目标。
3. 如果 cnt 统计出来的孤岛数量大于 1。那么我们需要挪动的线数量正好是 cnt - 1。

代码

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        m = len(connections)
        if m < n - 1: return -1
        p = [i for i in range(n)]

        cnt = n
        def find(x: int) -> int:
            if p[x] == x:
                return x
            px = find(p[x])
            p[x] = px #路径压缩，可以优化性能
            return px

        def union(x: int, y: int) -> int:
            px = find(x)
            py = find(y)

            if px != py:
                p[px] = py
                nonlocal cnt
                cnt -= 1

        for x, y in connections:
            union(x, y)

        return cnt - 1

时间复杂度： O(n log n)

空间复杂度： O(n)

[ZhangNN2018]

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1:
            return -1
        p = [[i] for i in range(n)]
        for x, y in connections:
            if p[x] is not p[y]:
                p[x].extend(p[y])
                for z in p[y]:
                    p[z] = p[x]
        return len({*map(id, p)}) - 1

[feifan-bai]

思路 1.As long as there are at least (n - 1) connections, there is a way to connect all computers. 2.DFS to find out the number of isolated computer clusters.

代码

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1: 
            return -1
        G = [set() for i in range(n)]
        for i, j in connections:
            G[i].add(j)
            G[j].add(i)
        seen = [0] * n

        def dfs(i):
            if seen[i]: return 0
            seen[i] = 1
            for j in G[i]: dfs(j)
            return 1

        return sum(dfs(i) for i in range(n)) - 1

复杂度分析

• 时间复杂度：O(N+M)
• 空间复杂度：O(N+M)

[zhangzz2015]

思路

• 采用union find 查找联通子图，每个联通子图的最大size，用weight记录，再对感染节点按照组进行分类，如果该节点所在的组只有1个节点，则删除后，感染数减少该组的节点数。如果有多个则无法减少。时间复杂度为O(n)，空间复杂度为O(n)。考虑follow up问题，如果可以允许删除最多删除k个节点，最小花最后的感染节点。

• 采用

关键点

代码

• 语言支持：C++

C++ Code:

class UF
{
vector<int> parent; 
vector<int> weight; 
int count; 
public: 
    UF(int n)
    {
        for(int i=0; i< n; i++)
        {
            parent.push_back(i); 
            weight.push_back(1); 
        }
        count = n; 
    }

    void uninTwoNode(int i, int j)
    {
        int parentI = findParent(i); 
        int parentJ = findParent(j); 
        if(parentI != parentJ)
        {
            if(weight[parentI] < weight[parentJ])
            {
                parent[parentI] = parentJ; 
                weight[parentJ] += weight[parentI]; 
                weight[parentI]=0 ; 
                count --; 
            }
            else
            {
                parent[parentJ] = parentI; 
                weight[parentI] += weight[parentJ]; 
                weight[parentJ]=0; 
                count--; 
            }
        }
    }
    int findParent(int i)
    {
        while(parent[i]!=i)
        {
            parent[i] = parent[parent[i]]; 
            i = parent[i]; 
        }
        return i; 
    }
    int getWeight(int i)
    {
        return weight[i]; 
    }

}; 
class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {

        UF uf(graph.size()); 
        for(int i=0; i< graph.size(); i++)
        {
            for(int j=i+1; j< graph[i].size(); j++)
            {
                if(graph[i][j])
                  uf.uninTwoNode(i, j);
            }
        }

        unordered_map<int, int> record;
        sort(initial.begin(), initial.end()); 
        int totalEffectNode =0; 
        for(int i=0; i< initial.size(); i++)
        {
            int rootNode =uf.findParent(initial[i]);  
            record[rootNode]++;
            if(record[rootNode]==1)
            {
                totalEffectNode += uf.getWeight(rootNode); 
            }
        }
        int minNum =INT_MAX;
        int ret =-1; 
        for(int i=0; i< initial.size(); i++)
        {
            int rootNode = uf.findParent(initial[i]); 
            if(record[rootNode]==1)
            {
                int effectNode = totalEffectNode - uf.getWeight(rootNode); 
                if(effectNode<minNum)
                {
                    minNum = effectNode; ; 
                    ret = initial[i]; 
                }
            }
            else
            {
                if(totalEffectNode < minNum)
                {
                    minNum = totalEffectNode; 
                    ret =initial[i]; 
                }
            }
        }
        return ret; 
    }
};

[Brent-Liu]

class Solution: def makeConnected(self, n: int, connections: List[List[int]]) -> int: if len(connections) < n - 1: return -1 G = [set() for i in range(n)] for i, j in connections: G[i].add(j) G[j].add(i) seen = [0] * n

    def dfs(i):
        if seen[i]: return 0
        seen[i] = 1
        for j in G[i]: dfs(j)
        return 1

    return sum(dfs(i) for i in range(n)) - 1

[zhangzz2015]

思路

• 利用最树的性质，对于n个节点，n-1条边可形成树，任意两个节点之间能形成通路，因此当边的数目少于n-1，则无法满足，返回-1，其他情况通过unionFind方法，建立联通图，找到group数目，因为需要移动group -1 条边，可把所有的group连接。时间复杂度为O(E)，空间复杂度为 O(V)，E为edge数目，V为 vertices的数目。

关键点

代码

• 语言支持：C++

C++ Code:

struct UF
{
   vector<int> parent;
    int numGroup; 
   UF(int n)
   {
      for(int i=0; i< n; i++)
          parent.push_back(i); 
      numGroup =n;  
   };

   void uninTwoNode(int inode, int jnode)
   {
       int iparent = findParent(inode); 
       int jparent = findParent(jnode); 
       if(iparent !=jparent)
       {
           parent[iparent] = jparent; 
           numGroup--; 
       }
   }

   int findParent(int inode)
   {
       while(inode!=parent[inode])
       {
           parent[inode] = parent[parent[inode]]; 
           inode = parent[inode]; 
       }
       return inode; 
   }

}; 
class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {

       //   tree   edge num  = n-1.  if edge < n-1.  return -1. 
       if(connections.size()<n-1) 
           return -1; 

       UF uf(n);  
       for(int i=0; i< connections.size(); i++)
       {
           int inode = connections[i][0]; 
           int jnode = connections[i][1]; 
           uf.uninTwoNode(inode, jnode);  
       }
       return uf.numGroup-1;         
    }
};

[rzhao010]

class Solution {
    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) {
            return -1;
        }

        UnionFind uf = new UnionFind(n);
        for (int[] conn: connections) {
            uf.unite(conn[0], conn[1]);
        }

        return uf.count - 1;
    }

    class UnionFind{
        int[] parent;
        int n;
        int count = 0;
        public UnionFind(int n ) {
            this.n = n;
            this.count = n;
            this.parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            return parent[x] == x ? x : (parent[x] = find(parent[x]));
        }

        public void unite(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) {
                return;
            }
            parent[y] = x;
            --count;
            return;
        }
    }
}

[moirobinzhang]

Code:

public class Solution { public int MakeConnected(int n, int[][] connections) { if (connections.Length < n - 1) return -1;

    UF uf = new UF(n);

    foreach(var coNode in connections)
        uf.Union(coNode[0], coNode[1]);

    return uf.component - 1;  
}

public class UF
{
    public int[] parent;
    public int component;

    public UF(int n)
    {
        parent = new int[n];
        component = n;

        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    public int Find(int x)
    {
        while( x != parent[x])
            x = parent[x];

        return parent[x];
    }

    public void Union(int x, int y)
    {
        int parentX = Find(x);
        int parentY = Find(y);

        if (parentX == parentY)
            return;

        parent[parentX] = parentY;
        component--;
    }
}

}

[mannnn6]

class Solution {
    List<Integer>[] edges;
    boolean[] used;

    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) {
            return -1;
        }

        edges = new List[n];
        for (int i = 0; i < n; ++i) {
            edges[i] = new ArrayList<Integer>();
        }
        for (int[] conn : connections) {
            edges[conn[0]].add(conn[1]);
            edges[conn[1]].add(conn[0]);
        }

        used = new boolean[n];
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (!used[i]) {
                dfs(i);
                ++ans;
            }
        }

        return ans - 1;
    }

    public void dfs(int u) {
        used[u] = true;
        for (int v : edges[u]) {
            if (!used[v]) {
                dfs(v);
            }
        }
    }
}

[yan0327]

func makeConnected(n int, connections [][]int) int {
    if len(connections) < n-1{
        return -1
    }
    groupNum := n
    parent := make([]int,n)
    var findRoot func(x int) int
    findRoot = func(x int)int{
        if x == parent[x]{
            return x
        }
        parent[x] = findRoot(parent[x])
        return parent[x]
    }
    for i:=0;i<len(parent);i++{
        parent[i] = i
    }
    for i:=0;i<len(connections);i++{
        aRoot := findRoot(connections[i][0])
        bRoot := findRoot(connections[i][1])
        if aRoot != bRoot{
            groupNum--
            parent[aRoot] = bRoot
        }
    }
    return groupNum-1
}

[Tesla-1i]

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        m = len(connections)
        if m < n - 1: return -1
        p = [i for i in range(n)]

        cnt = n
        def find(x: int) -> int:
            if p[x] == x:
                return x
            px = find(p[x])
            p[x] = px #路径压缩，可以优化性能
            return px

        def union(x: int, y: int) -> int:
            px = find(x)
            py = find(y)

            if px != py:
                p[px] = py
                nonlocal cnt
                cnt -= 1

        for x, y in connections:
            union(x, y)

        return cnt - 1

[declan92]

思路

1. 如果边的数量小于n-1,则返回-1;
2. 使用并查集求出初始连通分量的个数count;
3. 答案为count-1;

步骤

1. 建立并查集,统计连通分量的个数;

java

class Solution {
    public int makeConnected(int n, int[][] connections) {
        int len = connections.length;
        if (len < n - 1) {
            return -1;
        }
        UF uf = new UF(n);
        for (int i = 0; i < len; i++) {
            int[] con = connections[i];
            uf.union(con[0], con[1]);
        }
        return uf.count - 1;
    }
}

class UF {
    int[] parent;
    int count;

    public UF(int n) {
        parent = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

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

    public void union(int x, int y){
        int xRoot = find(x);
        int yRoot = find(y);
        if(xRoot == yRoot) return;
        parent[xRoot] = yRoot;
        count--;
    }
}

时间:O(m),m为边的数量
空间:O(n),n为顶点数

[xuhzyy]

class UnionFind:
    def __init__(self, n):
        self.father = {}
        self.count = 0
        for i in range(n):
            self.father[i] = i
            self.count += 1

    def find(self, x):
        root = x
        while(self.father[root] != root):
            root = self.father[root]
        while(self.father[x] != root):
            ori_father = self.father[x]
            self.father[x] = root
            x = ori_father
        return root

    def union(self, x, y):
        father_x = self.find(x)
        father_y = self.find(y)
        if father_x != father_y:
            self.father[father_x] = father_y
            self.count -= 1

class Solution(object):
    def makeConnected(self, n, connections):
        """
        :type n: int
        :type connections: List[List[int]]
        :rtype: int
        """
        if len(connections) < n - 1:
            return -1
        uf = UnionFind(n)
        for x, y in connections:
            uf.union(x, y)
        return uf.count - 1

[ZJP1483469269]

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        m = len(connections)
        p = [i for i in range(n)]
        size = 1
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]
        if m < n - 1:
            return -1
        else:
            for x ,y in connections:
                a , b = find(x) , find(y)
                if not a == b:
                    p[a] = b
                    size += 1
            print(size)
            return n-size

[googidaddy]

class Solution: def makeConnected(self, n: int, connections: List[List[int]]) -> int: if len(connections) < n - 1: return -1 p = [[i] for i in range(n)] for x, y in connections: if p[x] is not p[y]: p[x].extend(p[y]) for z in p[y]: p[z] = p[x] return len({*map(id, p)}) - 1

[james20141606]

Day 78: 1319. Number of Operations to Make Network Connected (DFS, BFS, union and find)

• Problem Link

  • 1319. Number of Operations to Make Network Connected

• Ideas

  • use Union and Find could solve the problem. We should find the sub-network within the network. The operation num is the operation to connect the sub-network.

• Complexity: hash table and bucket

  • Time: O(logX) and O(logY) X and Y are the find and union operation.
  • Space: O(V)

• Code

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        root = [i for i in range(n)]

        def find(p):
            while p != root[p]:
                root[p] = root[root[p]]
                p = root[p]

            return p

        def union(p, q):
            root[find(p)] = find(q)

        have = 0
        for connec in connections:
            a, b = connec
            if find(a) != find(b):
                union(a, b)
            else:
                have += 1

        diff_root = set()
        for i in range(n):
            diff_root.add(find(i))

        return len(diff_root) - 1 if have >= len(diff_root) - 1 else -1

• other resources:
  • https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/solution/lian-tong-wang-luo-de-cao-zuo-ci-shu-by-leetcode-s/

[tongxw]

思路

阅读理解题，其实跟省份数量那题思路一样的，先求连通分量，然后需要调整网线数就是连通分量数 - 1。 初始网线数至少为n-1

class Solution {
    public int makeConnected(int n, int[][] connections) {
        int m = connections.length;
        if (m < n-1) {
            return -1;
        }

        Map<Integer, Integer> parents = new HashMap<>();
        for (int i=0; i<n; i++) {
            parents.put(i, null);
        }

        int ans = n;
        for (int[] con: connections) {
            // find
            int root1 = find(parents, con[0]);
            int root2 = find(parents, con[1]);

            // union
            if (root1 != root2) {
                parents.put(root1, root2);
                ans--;
            }
        }

        return ans - 1;
    }

    private int find(Map<Integer, Integer> parents, int node) {
        int root = node;
        while (parents.get(root) != null) {
            root = parents.get(root);
        }

        while (node != root) {
            int oldParent = parents.get(node);
            parents.put(node, root);
            node = oldParent;
        }

        return root;
    }
}

TC: O(nlogn) SC: O(n)

[tian-pengfei]

class UnionFind{

    vector<int> parent;

public:
    UnionFind(int n){
        parent.resize(n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    void union_set(int i,int j){
        parent[find(i)] = find(j);
    }

    int find(int i){
        if(parent[i]!=i){
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }

};

class Solution {

public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        UnionFind uf(n);
        if(n>connections.size()+1){
            return -1;
        }
        for (auto & connection:connections){
            uf.union_set(connection[0],connection[1]);
        }

        unordered_set<int> set;
        for (int i = 0; i < n; ++i) {
            set.insert(uf.find(i));
        }
        for(const auto a:set){
            cout<<a<<endl;
        }
        return set.size()-1;
    }
};

[Bochengwan]

思路

利用dfs找到connected component, 需要联通的次数为n-1

代码

    def makeConnected(self, n, connections):
        if len(connections) < n - 1: return -1
        G = [set() for i in xrange(n)]
        for i, j in connections:
            G[i].add(j)
            G[j].add(i)
        seen = [0] * n

        def dfs(i):
            if seen[i]: return 0
            seen[i] = 1
            for j in G[i]: dfs(j)
            return 1

        return sum(dfs(i) for i in xrange(n)) - 1

复杂度分析

• 时间复杂度：O(len(connections))
• 空间复杂度：O(N)

[CoreJa]

思路

• UF：经典并查集，不要去想怎么移线缆，最小的移动次数一定是当前连通子图数-1。所以直接用并查集算连通子图数即可，前面要判断其connections总数是否满足让其全部连通。复杂度$O(E)$，顺便一提这个题如果不按秩合并的话速度会慢很多。

代码

class Solution:
    # UF：经典并查集，不要去想怎么移线缆，最小的移动次数一定是当前连通子图数-1。所以直接用并查集算连通子图数即可，前面要判
    # 断其connections总数是否满足让其全部连通。复杂度$O(E)$，顺便一提这个题如果不按秩合并的话速度会慢很多。
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1:
            return -1
        uf = {i: i for i in range(n)}
        size = {i: 1 for i in range(n)}

        def find(x):
            if uf[x] != x:
                uf[x] = find(uf[x])
            return uf[x]

        count = n
        for a, b in connections:
            p, q = find(a), find(b)
            if p != q:
                count -= 1
                if size[p] > size[q]:
                    size[p] += size[q]
                    uf[q] = p
                else:
                    size[q] += size[p]
                    uf[p] = q
        return count - 1

[haixiaolu]

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.n = n 
        self.setCount = n

    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False 
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.parent[y] = x
        self.size[x] += self.size[y]
        self.setCount -= 1
        return True 

    def isConnected(self, x, y):
        return self.find(x) == self.find(y)

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1:
            return -1

        uf = UnionFind(n)
        for x, y in connections:
            uf.union(x, y)

        return uf.setCount - 1

[LannyX]

思路

Union Find

代码

class Solution {
    public int makeConnected(int n, int[][] connections) {
        if(n - 1 > connections.length){
            return -1;
        }
        UnionFind unionFind = new UnionFind(n);
        for(int[] c : connections){
            unionFind.union(c[0], c[1]);
        }
        return unionFind.cnt - 1;
    }
    class UnionFind{
        public int cnt;
        public int[] parents;

        public UnionFind(int n){
            this.cnt = n;
            this.parents = new int[n];
            for(int i = 0; i < n; i++){
                parents[i] = i;
            }
        }

        public void union(int x, int y){
            int x_root = find(x);
            int y_root = find(y);
            if(x_root != y_root){
                cnt--;
            }
            parents[x_root] = y_root;
        }
        public int find(int x){
            if(x == parents[x]){
                return x;
            }
            parents[x] = find(parents[x]);
            return parents[x];
        }
    }
}

[superduduguan]

class Solution: def makeConnected(self, n: int, connections: List[List[int]]) -> int: if len(connections) < n - 1: return -1 G = [set() for i in range(n)] for i, j in connections: G[i].add(j) G[j].add(i) seen = [0] * n

    def dfs(i):
        if seen[i]: return 0
        seen[i] = 1
        for j in G[i]: dfs(j)
        return 1

    return sum(dfs(i) for i in range(n)) - 1

[xinhaoyi]

class Solution{ /对于无向图的n个顶点，要组成一个连通图，至少需要n-1条边。如果我们把每个节点都看作一个连通分量，一个具有n个节点的集合，就相当于有n个连通分量（每个连通分量是仅有一个顶点的图），至少需要n-1条边组成一个连通图。 一般地，如果一个图的连通分量数为m,那么将这些连通分量组成一个连通图至少需要m-1条边。 这个题就化解成了求m-1的问题，即求连通分量，于是我们首先想到要用并查集求解连通分量的问题。/ public int makeConnected(int n, int[][] connections) { if(connections.length<n-1) return -1;//连通图的边数至少为n-1 UFS ufs=new UFS(n); for(int[] edge:connections) { ufs.union(edge[0], edge[1]); } return ufs.UnionCount-1; } } class UFS{ int[] father; int UnionCount; public UFS(int n) { father=new int[n]; this.UnionCount=n; for(int i=0;i<n;i++) father[i]=i;//初始化 } public int find(int i) {//查 if(i!=father[i]) father[i]=find(father[i]); return father[i]; } public void union(int x,int y) {//并 int Fx=find(x); int Fy=find(y); if(Fy==Fx) return; father[Fx]=Fy; UnionCount--; } }

[jiaqiliu37]

··· class Solution: def makeConnected(self, n: int, connections: List[List[int]]) -> int: root = [i for i in range(n)]

    def find(p):
        while p != root[p]:
            root[p] = root[root[p]]
            p = root[p]

        return p

    def union(p, q):
        root[find(p)] = find(q)

    have = 0
    for connec in connections:
        a, b = connec
        if find(a) != find(b):
            union(a, b)
        else:
            have += 1

    diff_root = set()
    for i in range(n):
        diff_root.add(find(i))

    return len(diff_root) - 1 if have >= len(diff_root) - 1 else -1

···

[falconruo]

思路:

并查集

复杂度分析:

• 时间复杂度: O(N)，N为computer个数
• 空间复杂度: O(N)

代码(C++):

class DSU {
public:
    vector<int> root;
    int network;
    DSU(int n) {
        root.resize(n);
        for (int i = 0; i < n; i++)
            root[i] = i;
        network = n;
    }

    int Find(int x) {
        if (x != root[x])
            root[x] = Find(root[x]);

        return root[x];
    }

    void Union(int x, int y) {
        int rx = Find(x);
        int ry = Find(y);

        if (rx != ry) {
            root[rx] = ry;
            network--;
        }
    }
};

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

        DSU dsu(n);

        for (auto c : connections)
            dsu.Union(c[0], c[1]);

        return dsu.network - 1;
    }
};

[xjhcassy]

class Solution {
    public int makeConnected(int n, int[][] connections) {
        if (n - 1 > connections.length) {
            return -1;
        }
        UnionFind unionFind = new UnionFind(n);
        for (int[] connection : connections) {
            unionFind.union(connection[0], connection[1]);
        }
        return unionFind.cnt - 1;
    }

    class UnionFind {
        public int cnt;
        public int[] parents;

        public UnionFind(int n) {
            this.cnt = n;
            this.parents = new int[n];
            for (int i = 0; i < n; i++) {
                parents[i] = i;
            }
        }

        public void union(int x, int y) {
            int x_root = find(x);
            int y_root = find(y);
            if (x_root != y_root) {
                cnt--;
            }
            parents[x_root] = y_root;
        }

        public int find(int x) {
            if (x == parents[x]) {
                return x;
            }
            parents[x] = find(parents[x]);
            return parents[x];
        }
    }
}

[Today-fine]

学习官方代码

// 并查集模板
class UnionFind {
public:
    vector<int> parent;
    vector<int> size;
    int n;
    // 当前连通分量数目
    int setCount;

public:
    UnionFind(int _n): n(_n), setCount(_n), parent(_n), size(_n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int findset(int x) {
        return parent[x] == x ? x : parent[x] = findset(parent[x]);
    }

    bool unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x == y) {
            return false;
        }
        if (size[x] < size[y]) {
            swap(x, y);
        }
        parent[y] = x;
        size[x] += size[y];
        --setCount;
        return true;
    }

    bool connected(int x, int y) {
        x = findset(x);
        y = findset(y);
        return x == y;
    }
};

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

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

        return uf.setCount - 1;
    }
};

[guangsizhongbin]

type unionFind struct { parent, size []int setCount int // 当前连通分量数目 }

func newUnionFind(n int) *unionFind { parent := make([]int, n) size := make([]int, n) for i := range parent { parent[i] = i size[i] = 1 } return &unionFind{parent, size, n} }

func (uf *unionFind) find(x int) int { if uf.parent[x] != x { uf.parent[x] = uf.find(uf.parent[x]) } return uf.parent[x] }

func (uf *unionFind) union(x, y int) { fx, fy := uf.find(x), uf.find(y) if fx == fy { return } if uf.size[fx] < uf.size[fy] { fx, fy = fy, fx } uf.size[fx] += uf.size[fy] uf.parent[fy] = fx uf.setCount-- }

func makeConnected(n int, connections [][]int) int { if len(connections) < n-1 { return -1 }

uf := newUnionFind(n)
for _, c := range connections {
    uf.union(c[0], c[1])
}

return uf.setCount - 1

}

[callmeerika]

思路

并查集

代码

var City = function (n) {
    this.parent = {};
    this.size = {};
    this.setCount = 0;
    this.init(n);
};

City.prototype.init = function (n) {
    for (let i = 0; i < n; i++) {
        this.parent[i] = i;
        this.size[i] = 1;
    }
    this.setCount = n;
};

City.prototype.find = function (x) {
    while (x != this.parent[x]) x = this.parent[x];
    return x;
};

City.prototype.connected = function (x, y) {
    const a = this.find(x);
    const b = this.find(y);
    return a === b;
};

City.prototype.unite = function (x, y) {
    let a = this.find(x);
    let b = this.find(y);
    if (a === b) {
        return;
    }
    if (this.size[a] < this.size[b]) {
        [a, b] = [b, a];
    }
    this.parent[b] = a;
    this.size[a] += this.size[b];
    this.setCount -= 1;
};

var makeConnected = function(n, connections) {
    if (connections.length < n - 1) {
        return -1;
    }
    const res = new City(n);
    for (const vv of connections) {
        res.unite(vv[0], vv[1]);
    }
    return res.setCount - 1;
};

复杂度

时间复杂度：O(mn) 空间复杂度：O(n)

[Richard-LYF]

class Solution: def makeConnected(self, n: int, connections: List[List[int]]) -> int: root = [i for i in range(n)]

    def find(p):
        while p != root[p]:
            root[p] = root[root[p]]
            p = root[p]

        return p

    def union(p, q):
        root[find(p)] = find(q)

    have = 0
    for connec in connections:
        a, b = connec
        if find(a) != find(b):
            union(a, b)
        else:
            have += 1

    diff_root = set()
    for i in range(n):
        diff_root.add(find(i))

    return len(diff_root) - 1 if have >= len(diff_root) - 1 else -1

[rockydale]

const makeConnected = function(n, connections) {
    if (connections.length < n - 1) {
        return -1;
    }
    let groupNum = n;
    let parent = new Array(n);

    const findRoot = (x) => {
        if (x == parent[x]) { 
            return x;
        }
        parent[x] = findRoot(parent[x]);
        return parent[x];
    }

    for (let i = 0; i < parent.length; i++) {
        parent[i] = i; 
    }

    for (let i = 0; i < connections.length; i++) { 
        const aRoot = findRoot(connections[i][0]); 
        const bRoot = findRoot(connections[i][1]); 
        if (aRoot != bRoot) {
            groupNum--;  
            parent[aRoot] = bRoot;
        }
    }
    return groupNum - 1;
};

[dahaiyidi]

Problem

[1319. 连通网络的操作次数](https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/)

用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。

---

Note

• 并查集

---

Complexity

• 时间O：O(m⋅α(n))，其中 m是数组 connections的长度，α是阿克曼函数的反函数。
• 空间O：n

---

Python

C++

class UnionFind{
public:
    vector<int> size; // set的size， 有时为set 树的高度？
    vector<int> parent; // 父节点
    int n;  // 节点数
    int setCount;// 有多少个set

public:
    UnionFind(int _n): size(_n, 1), parent(_n), n(_n), setCount(_n) {
        iota(parent.begin(), parent.end(), 0);  // 将parent的元素按顺序设置为0，1，2，3，4
    }
    int findset(int x) {
        // 找到根节点
        return x == parent[x] ? x: parent[x] = findset(parent[x]);
    }
    // int findset(int x) {
    //     return parent[x] == x ? x : parent[x] = findset(parent[x]);
    // }

    bool unite(int x, int y){
        x = findset(x);
        y = findset(y);

        // 若已经在同一个set中
        if(x == y){
            return false;
        }
        // 若不在同一个set中，则需要合并
        // 保证size[x] >= size[y]
        if(size[x] < size[y]){
            swap(x, y);
        }
        // 将y的parent设置为x
        parent[y] = x;
        size[x] += size[y];
        setCount--; // set数量-1
        return true; // 合并成功
    }
};

class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        if(connections.size() < n-1){
            return -1;
        }
        // 至此肯定可以联通
        UnionFind uf(n);
        for(auto const& item: connections){
            uf.unite(item[0], item[1]); 
        }
        return uf.setCount - 1;

    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

[wdwxw]

class Solution { List[] edges; boolean[] used;

public int makeConnected(int n, int[][] connections) {
    if (connections.length < n - 1) {
        return -1;
    }

    edges = new List[n];
    for (int i = 0; i < n; ++i) {
        edges[i] = new ArrayList<Integer>();
    }
    for (int[] conn : connections) {
        edges[conn[0]].add(conn[1]);
        edges[conn[1]].add(conn[0]);
    }

    used = new boolean[n];
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs(i);
            ++ans;
        }
    }

    return ans - 1;
}

public void dfs(int u) {
    used[u] = true;
    for (int v : edges[u]) {
        if (!used[v]) {
            dfs(v);
        }
    }
}

}

[fornobugworld]

class Solution: def makeConnected(self, n: int, connections: List[List[int]]) -> int: root = [i for i in range(n)]

    def find(p):
        while p != root[p]:
            root[p] = root[root[p]]
            p = root[p]

        return p

    def union(p, q):
        root[find(p)] = find(q)

    have = 0
    for connec in connections:
        a, b = connec
        if find(a) != find(b):
            union(a, b)
        else:
            have += 1

    diff_root = set()
    for i in range(n):
        diff_root.add(find(i))

    return len(diff_root) - 1 if have >= len(diff_root) - 1 else -1

[Hacker90]

class Solution: def makeConnected(self, n: int, connections: List[List[int]]) -> int: root = [i for i in range(n)]

def find(p):
    while p != root[p]:
        root[p] = root[root[p]]
        p = root[p]

    return p

def union(p, q):
    root[find(p)] = find(q)

have = 0
for connec in connections:
    a, b = connec
    if find(a) != find(b):
        union(a, b)
    else:
        have += 1

diff_root = set()
for i in range(n):
    diff_root.add(find(i))

return len(diff_root) - 1 if have >= len(diff_root) - 1 else -1

[kite-fly6618]

思路

并查集

代码

var makeConnected = function(n, connections) {
    if (connections.length < n - 1) {
        return -1;
    }
    let groupNum = n;
    let parent = new Array(n);

    const findRoot = (x) => {
        if (x == parent[x]) { 
            return x;
        }
        parent[x] = findRoot(parent[x]);
        return parent[x];
    }

    for (let i = 0; i < parent.length; i++) {
        parent[i] = i; 
    }

    for (let i = 0; i < connections.length; i++) { 
        const aRoot = findRoot(connections[i][0]); 
        const bRoot = findRoot(connections[i][1]); 
        if (aRoot != bRoot) {
            groupNum--;  
            parent[aRoot] = bRoot;
        }
    }
    return groupNum - 1;
};

复杂度

时间复杂度:O(mn)
空间复杂度:O(n)

[yetfan]

思路 先判断线够不够多，不够返回-1。查并集，返回集合总数-1

代码

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        l = len(connections)
        if n > l + 1:
            return -1

        uf = UnionFind()
        for i in range(n):
            uf.add(i)
        for i,j in connections:
            uf.merge(i,j)
        return uf.num_of_sets - 1

class UnionFind:
    def __init__(self):
        self.father = {}
        self.num_of_sets = 0

    def find(self,x):
        root = x
        while self.father[root] != None:
            root = self.father[root]

        while x != root:
            original_father = self.father[x]
            self.father[x] = root
            x = original_father

        return root

    def merge(self,x,y):
        root_x,root_y = self.find(x),self.find(y)

        if root_x != root_y:
            self.father[root_x] = root_y
            self.num_of_sets -= 1

    def add(self,x):
        if x not in self.father:
            self.father[x] = None
            self.num_of_sets += 1

复杂度 时间 O(n*l) 空间 O(n)

[hdyhdy]

func makeConnected(n int, connections [][]int) (ans int) {
    if len(connections) < n-1 {
        return -1
    }

    graph := make([][]int, n)
    for _, c := range connections {
        v, w := c[0], c[1]
        graph[v] = append(graph[v], w)
        graph[w] = append(graph[w], v)
    }

    vis := make([]bool, n)
    var dfs func(int)
    dfs = func(from int) {
        vis[from] = true
        for _, to := range graph[from] {
            if !vis[to] {
                dfs(to)
            }
        }
    }
    for i, v := range vis {
        if !v {
            ans++
            dfs(i)
        }
    }
    return ans - 1
}

[ZacheryCao]

idea

Union Find

Code

class UF{
private:
    vector<int> parent;
    vector<int> size;
    int cont;
public:
    UF(int n){
        cont = n;
        for(int i = 0; i < n; i++){
            parent.push_back(i);
            size.push_back(1);
        }

    }

    int find(int p){
        while(parent[p]!=p){
            parent[p] = find(parent[p]);
            return parent[p];
        }
        return p;
    }

    bool connected(int p, int q){
        return find(p) == find(q);
    }

    void union_group(int p, int q){
        int parent_p = find(p);
        int parent_q = find(q);
        if(parent_p != parent_q){
            if(size[parent_p]< size[parent_q]){
                size[parent_q] += size[parent_p];
                parent[parent_p] = parent_q;
            }else{
                size[parent_p] += size[parent_q];
                parent[parent_q] = parent_p;
            }
            cont--;
        }
    }

    int groups(){
        return cont;
    }

};

class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        UF uf(n);
        for(int i = 0; i < connections.size(); i++){
            int p = connections[i][0];
            int q = connections[i][1];
            if(!uf.connected(p, q)) uf.union_group(p, q);
        }
        int required = uf.groups() -1;
        if(n>connections.size()+1) return -1;
        return required;
    }
};

Complexity

Time: O(len(connections)+n) Space: O(n)

[codingPitaya]

var makeConnected = function(n, connections) {
    if(connections.length < n-1) return -1;
    const map = new UnionFind(n);
    for(const [x,y] of connections) {
        if(!map.connected(x,y)) map.union(x,y);
    }
    return map.count-1;
};
class UnionFind {
    constructor(size) {
        this.root = new Array(size).fill(0).map((_,index)=>index);
        this.rank = this.root.slice();
        this.count = size;
    }

    find(x){
        if(x === this.root[x]) return x;
        return (this.root[x] = this.find(this.root[x]));
    }

    union(x,y) {
        const _root = this.root;
        const _rank = this.rank;
        const rootX = this.find(x);
        const rootY = this.find(y);

        if(rootX !== rootY) {
            if(_rank[x] < _rank[y]) {
                _root[rootX] = rootY;
            }else if(_rank[x] > _rank[y]) {
                _root[rootY] = rootX;
            }
            this.count--;
        }
    }

    connected(x,y){
        return this.find(x) === this.find(y);
    }
}

[for123s]

class Solution {
public:
    vector<int> parent;
    int count;
    int find(int x)
    {
        if(x!=parent[x])
        {
            parent[x] = find(parent[x]);
            return parent[x];
        }
        return x;
    }

    int makeConnected(int n, vector<vector<int>>& connections) {
        if(n>connections.size()+1)
            return -1;
        for(int i=0;i<n;i++)
            parent.push_back(i);
        count = n;
        for(int i=0;i<connections.size();i++)
            if(find(connections[i][0])!=find(connections[i][1]))
            {
                parent[find(connections[i][0])] = find(connections[i][1]);
                count--;
            }
        return count-1;
    }
};

[zzzpppy]

class Solution {
    int[] father;
    int[] sz;
    int num;

    public int find(int p) {
        if (p != father[p]) {
            p = find(father[p]);
        }
        return p;
    }
    public void union(int p, int q) {
        int i = find(p);
        int j = find(q);
        if (i == j) return;
        num -= 1;
        if (sz[i] < sz[j]) {
            father[i] = j;
            sz[j] += sz[i];
        } else {
            father[j] = i;
            sz[i] += sz[j];
        }
    }

    public void initUF(int n) {
        father = new int[n];
        sz = new int[n];
        num = n;
        for (int i = 0; i < n; i++) {
            father[i] = i;
            sz[i] = 1;
        }
    }
    public int makeConnected(int n, int[][] connections) {
        initUF(n);
        // 多余的线缆数量
        int cnt = 0;
        for (int[] c : connections) {
            int f = c[0], t = c[1];
            // 两个点已经连通，不需要这个线缆
            if (find(f) == find(t)) {
                cnt += 1;
                continue;
            }
            union(f, t);
        }
        // 所需要的线缆数量
        int cnt2 = num - 1;
        if (cnt < cnt2) {
            return -1;
        }
        return cnt2;
    }
}

[taojin1992]

/*

# Understand:
1 <= n <= 10^5
1 <= connections.length <= min(n*(n-1)/2, 10^5)
connections[i].length == 2
0 <= connections[i][0], connections[i][1] < n
connections[i][0] != connections[i][1]
There are no repeated connections.
No two computers are connected by more than one cable.

0 - (n-1) represents computers

n computers -> at least we need n - 1 connections

- Input: n = 4, connections = [[0,1],[0,2],[1,2]]

2 unions, connection number = 3, res = 1

- Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
3 unions, 5 connections, res = 2 -> we need 2 more connections

- Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
at least we need 6-1 = 5 connections, only have 4, return -1

- Input: n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
1 union, no need to reconnect

# Match & Plan:
int numConnectionsGiven = connections.length;
if (numConnectionsGiven < n - 1) return -1;

construct union find with path compression, keep track of # of unions

final res = # unions - 1

# Reivew:
4
[[0,1],[0,2],[1,2]]

returns 1

# Evaluate:

## Time:
O(connections.length) + O(n)

1 <= n <= 10^5
1 <= connections.length <= min(n*(n-1)/2, 10^5)

therefore, bounded by O(n)

## Space:
O(n)

*/

class Solution {

    class UF {
        int numOfUnions;
        int[] parent;
        int[] size;

        UF(int numOfElements) {
            numOfUnions = numOfElements;
            parent = new int[numOfElements];
            size = new int[numOfElements];

            for (int i = 0; i < numOfElements; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        // find the representative for x
        int find(int x) {
            while (x != parent[x]) {
                // make x as its parent's sibling
                parent[x] = parent[parent[x]];
                x = parent[x];// move up
            }
            return x;
        }

        // include both path compression and union by rank/size
        void union(int p, int q) {
            int headOfP = find(p);
            int headOfQ = find(q);
            if (headOfP == headOfQ) {
                return;
            }
            // attach the smaller to larger union
            if (size[headOfP] < size[headOfQ]) {
                parent[headOfP] = headOfQ;
                size[headOfQ] += size[headOfP];
            } else {
                parent[headOfQ] = headOfP;
                size[headOfP] += size[headOfQ];
            }
            numOfUnions--;
        }

        boolean connected(int p, int q) {
            return find(p) == find(q);
        }

    }
    public int makeConnected(int n, int[][] connections) {
        int numConnectionsGiven = connections.length;
        if (numConnectionsGiven < n - 1) return -1;
        UF unionFindObj = new UF(n);
        // make unions
        for (int[] connection : connections) {
            int p = connection[0];
            int q = connection[1];
            unionFindObj.union(p, q);
        }
        return unionFindObj.numOfUnions - 1;
    }

}

[hulichao]

思路

三个连通块要想联通至少得需要两条边（也就是两条线）那么不难看出最终结果就是连通块数量

代码

class Solution {

    private int[] parent;

    public int makeConnected(int n, int[][] connections) {
        // n 个节点相互连通至少需要n-1条线
        if (connections.length < n - 1) {
            return -1;
        }
        // 初始化
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        // 合并
        for (int[] connection : connections) {
            union(connection[0], connection[1]);
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (parent[i] == i) {
                count++;
            }
        }
        return count - 1;
    }

    private int find(int node) {
        return parent[node] == node ? node : (parent[node] = find(parent[node]));
    }

    private void union(int node1, int node2) {
        int root1 = find(node1);
        int root2 = find(node2);
        if (root1 == root2) {
            return;
        }
        parent[root1] = root2;
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[1149004121]

1319. 连通网络的操作次数

思路

并查集。N个结点要联通，至少要N - 1条边，如果connections的长度小于n-1则直接返回-1；如果长度大于n-1，则说明边有余裕，要修改边的个数取决于无法构成连通的结点个数，最初n个结点都不想连，缺n-1条边，没连通一个不在已有连通结点中的结点，则-1。

代码

var makeConnected = function (n, connections) {
    if(connections.length + 1 < n) return -1;
    let count = n - 1;
    let parent = new Array(n).fill(1).map((item, index) => index);
    for(let connect of connections){
        union(...connect);
    };
    return count;

    function find(x){
        if(parent[x] !== x){
            parent[x] = find(parent[x]);
        };
        return parent[x];
    }

    function union(x, y){
        let rootX = find(x);
        let rootY = find(y);
        if(rootX !== rootY){
            parent[rootX] = rootY;
            count--;
        }
    }
}

复杂度分析

• 时间复杂度：O(N) 。
• 空间复杂度：O(N) 。