【Day 78 】2021-11-26 - 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]
没有重复的连接。
两台计算机不会通过多条线缆连接。

[septasset]

思考

并查集

关键点

全联通网络代表只有一个联通域，并查集的变化和如何使用

代码(Python)

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        uf = UF(n)
        for lst in connections:
            v1 = lst[0]
            v2 = lst[1]
            uf.union(v1, v2)
        total = 0
        for val in uf.more_cables.values():
            total += val
        # print(uf.cnt, total)
        return uf.cnt - 1 if total >= uf.cnt - 1 else -1

class UF:
    def __init__(self, M):
        self.parent = {}
        self.more_cables = {}
        self.cnt = 0
        # 初始化 parent，size 和 cnt
        # cnt 是整数，表示一共有多少个联通域
        for i in range(M):
            self.parent[i] = i
            self.cnt += 1
            self.more_cables[i] = 0

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
        return x
    def union(self, p, q):
        if self.connected(p, q): 
            self.more_cables[self.find(p)] += 1
            return
        # 小的树挂到大的树上， 使树尽量平衡
        leader_p = self.find(p)
        leader_q = self.find(q)
        if leader_p >= leader_q:
            self.parent[leader_p] = leader_q
        else:
            self.parent[leader_q] = leader_p
        self.cnt -= 1
    def connected(self, p, q):
        return self.find(p) == self.find(q)

复杂度分析

• 时间：O(logn)
• 空间：O(n)

[jiahui-z]

思路: dfs

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

        List<Integer>[] graph = new List[n]; // build the graph in adjacency list
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<Integer>();
        }

        for (int[] connection : connections) {
            graph[connection[0]].add(connection[1]);
            graph[connection[1]].add(connection[0]);
        }

        boolean[] visited = new boolean[n];
        int components = 0; // the number of inter-connected components 
        for (int u = 0; u < n; u++) {
            if (!visited[u]) {
                dfs(u, graph, visited);
                components++;
            }
        }

        return components - 1; // we don't need to know where to remove and place cables, just the number of them
    }

    private void dfs(int node, List<Integer>[] graph, boolean[] visited) {
        if (visited[node]) return; // the node has been visited, do nothing
        visited[node] = true; // mark the node as visited
        for (int v : graph[node]) { // iterate all connected nodes for this node
            dfs(v, graph, visited);
        }
    }
}

Time Complexity: O(n+m), m is the length of connections Space Complexity: O(n)

[florenzliu]

Explanation

• graph + dfs: find number of connected components, add edges among them

Code

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n-1:
            return -1
        adj = defaultdict(list)
        for a, b in connections:
            adj[a].append(b)
            adj[b].append(a)

        def dfs(n):
            visited.add(n)
            for i in adj[n]:
                if i not in visited:
                    dfs(i)

        visited = set()
        count = 0
        for i in range(n):
            if i not in adj:
                count += 1
                continue
            if i not in visited:
                dfs(i)
                count += 1
        return count-1

Complexity

• Time: O(v+e)
• Space: O(v+e)

[okbug]

// 并查集模板
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;
    }
};

[Daniel-Zheng]

思路

并查集。

代码(C++)

class UnionFind {
public:
    vector<int> parent;
    vector<int> size;
    int n;
    int setCount;

    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;
    }
};

复杂度分析

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

[RonghuanYou]

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 connection in connections:
            a, b = connection
            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

[m-z-w]

var makeConnected = function(n, connections) {
    if (connections.length < n - 1) {
        return -1;
    }

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

    return uf.setCount - 1;
};

// 并查集模板
class UnionFind {
    constructor (n) {
        this.parent = new Array(n).fill(0).map((element, index) => index);
        this.size = new Array(n).fill(1);
        console.log(this.parent)
        // 当前连通分量数目
        this.setCount = n;
    }

    findset (x) {
        if (this.parent[x] === x) {
            return x;
        }
        this.parent[x] = this.findset(this.parent[x]);
        return this.parent[x];
    }

    unite (a, b) {
        let x = this.findset(a), y = this.findset(b);
        if (x === y) {
            return false;
        }
        if (this.size[x] < this.size[y]) {
            [x, y] = [y, x];
        }
        this.parent[y] = x;
        this.size[x] += this.size[y];
        this.setCount -= 1;
        return true;
    }

    connected (a, b) {
        const x = this.findset(a), y = this.findset(b);
        return x === y;
    }
}

[KennethAlgol]

const makeConnected = function(n, connections) {
    let edges = connections.length;
    if(edges < n-1) return -1;
    let g = [];
    for(let i=0;i<n;i++) g[i] = []
    for(let i=0;i<edges;i++){
        g[connections[i][0]].push(connections[i][1]);
        g[connections[i][1]].push(connections[i][0]);
    } 
    let v = Array(n).fill(0),c=0;
    for(let i=0;i<n;i++){
        if(!v[i]){
            c++;
            dfs(i,g,v)
        }
    }
    return c-1;
};

function dfs(i,con,v){
    v[i] = 1;
    for(let x of con[i]){
        if(!v[x]) dfs(x,con,v)
    }
}

[HouHao1998]

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);
            }
        }
    }
}

[learning-go123]

思路

• 并查集

代码

• 语言支持：Go

Go Code:

type UF struct {
    fa    []int
    count int
}

func (u *UF) init(N int) {
    u.fa = make([]int, N)
    for i := 0; i < N; i++ {
        u.fa[i] = i
    }
    u.count = N
}

func (u *UF) find(x int) int {
    for u.fa[x] != x {
        u.fa[x] = u.fa[u.fa[x]]
        x = u.fa[x]
    }
    return x
}

func (u *UF) union(p, q int) {
    p = u.find(p)
    q = u.find(q)
    if p == q {
        return
    }
    u.fa[p] = q
    u.count--
}

func makeConnected(n int, connections [][]int) int {
    if len(connections) < n-1 {
        return -1
    }
    u := &UF{}
    u.init(n)
    for _, c := range connections {
        u.union(c[0], c[1])
    }
    return u.count - 1
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(n)$

[chen445]

代码

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        union_map=list(range(n))
        extra_connections=0
        def find(a):
            while union_map[a] !=a:
                a=union_map[a]
            return a
        def union(a,b):
            nonlocal extra_connections
            root_a=find(a)
            root_b=find(b)
            if root_a != root_b:
                union_map[root_a]=root_b
            else:
                extra_connections+=1
        for connection in connections:
            union(connection[0],connection[1]) 
        group=set()
        for i in range(n):
            group.add(find(i))

        if len(group)-1 <= extra_connections:
            return len(group)-1
        else:
            return -1

复杂度

Time: O(M*logn) M is the length of connections

Space: O(N)

[carterrr]

class 联通网络的操作次数_1319 {
    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++ ) {
            uf.union(connections[i][0], connections[i][1]);
        }
        // 不用判断哪些线多余 和 缺少的线对比  
        // 两两连接n 个节点刚好要n - 1 根线  线的数量够就一定能移动 联通分量数量 -1 根使得构成一整个大联通分量
        return uf.size - 1;
    }

    private class UF{
        int[] root;
        int size;

        public UF(int n){
            size = n;
            root = new int[n];
            while(n > 0) {
                root[--n] = n;
            }
        }

        public int findRoot(int p) {
            if(root[p] == p) return p;
            return root[p] = findRoot(root[p]);
        }

        public void union(int p, int q) {
            int pRoot = findRoot(p);
            int qRoot = findRoot(q);
            if(pRoot != qRoot) {
                root[pRoot] = qRoot;
                size --;
            }
        }
    }
}

[machuangmr]

class Solution {
    public int makeConnected(int n, int[][] connections) {
    if (connections.length < n - 1) return -1;
        int size[] = new int[n];
        int parent[] = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            size[i] = 1;
            parent[i] = i;
        }
        for (int[] connection : connections) {
            int x = connection[0];
            int y = connection[1];
            union(x, y, parent, size);
        }
        return --count;
    }
     int count;

    private void union(int x, int y, int parent[], int size[]) {
        int fx = find(x, parent);
        int fy = find(y, parent);
        if (fx == fy) {
            return;
        } else {
            if (size[fx] >= size[fy]) {
                parent[fy] = fx;
                size[fx] += size[fy];
            } else {
                parent[fx] = fy;
                size[fy] += size[fx];
            }
            count--;
        }
    }

    private int find(int x, int parent[]) {
        if (parent[x] != x) {
            int father = find(parent[x], parent);
            parent[x] = father;
        }
        return parent[x];
    }
}

复杂度

• 时间复杂度O(1)
• 空间复杂度 O(n)

[ZJP1483469269]

思路

并查集

代码

class Solution {
    public int makeConnected(int n, int[][] connections) {
        UFS ufs = new UFS(n);
        for(int i = 0 ;i < connections.length;i++){
            ufs.union(connections[i][0],connections[i][1]);
        }
        int rest = ufs.getrest(),count = ufs.getcount();
        if(rest+1 < count) return -1;
        return count-1;
    }
    class UFS{
        int[] p;
        int[] sz;
        int count;
        int rest=0;
        UFS(int n){
            count =n;
            p = new int[n];
            sz = new int[n];
            for(int i = 0 ; i < n;i++){
                p[i] = i;
                sz[i] = 1;
            }    
        }

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

        public void union(int x,int y ){

            int xr = find(x);
            int yr = find(y);
            if(xr != yr){
                p[xr] = yr;
                sz[yr] += sz[xr];
                count--;
            }else{
                rest++;
            }
        }

        public int  size(int x){
            return sz[find(x)];
        }

        public int getrest(){
            return rest;
        }

        public int getcount(){
            return count;
        }

    }
}

复杂度分析

时间复杂度：O（max(n,m)）m为connections.length 空间复杂度：O（n）

[Zhi22]

Union Find

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        def find(x: int):
            while root[x] != x:
                root[x] = root[root[x]]
                x = root[x]
            return root[x]

        def union(x: int, y: int):
            nonlocal cnt
            if find(x) != find(y):
                root[find(x)] = find(y)
                cnt -= 1

        if len(connections) < n-1:
            return -1
        root = [i for i in range(n)]
        cnt = n
        for c in connections:
            union(c[0], c[1])
        return cnt - 1

时间复杂度: O(V+E)

空间复杂度 : O(N)

[asterqian]

思路

用并查集，如果可用的连接线小于电脑数量-1的话直接返回-1因为不可能全部连上，否则返回连通分量-1，比如你有三个连通分量，那么需要两条线再连接。

代码

class Solution {
public:
    int find(vector<int>& parent, int idx) {
        while (parent[idx] != idx) {
            parent[idx] = parent[parent[idx]];
            idx = parent[idx];
        }
        return idx;
    }
    int getUnion(vector<int>& parent, vector<int>& size, int rep1, int rep2) {
        rep1 = find(parent, rep1);
        rep2 = find(parent, rep2);
        if (rep1 == rep2) {
            return 0;
        } else {
            if (size[rep1] > size[rep2]) {
                size[rep1] += size[rep2];
                parent[rep2] = rep1;
            } else {
                size[rep2] += size[rep1];
                parent[rep1] = rep2;
            }
            return 1;
        }
    }
    int makeConnected(int n, vector<vector<int>>& connections) {
        if (connections.size() < n - 1) return -1;
        vector<int> reps(n);
        vector<int> size(n);
        for (int i = 0; i < n; ++i) {
            reps[i] = i;
            size[i] = 1;
        }
        int groupCnt = n;
        for (int i = 0; i < connections.size(); ++i) {
            groupCnt -= getUnion(reps, size, connections[i][0], connections[i][1]);
        }
        return groupCnt - 1;
    }
};

时间复杂度 O(α(n)M) M is the connections.size()

空间复杂度 O(n)

[yj9676]

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);
            }
        }
    }
}

[HWFrankFung]

Codes

 var makeConnected = function (n, connections) {
    const len = connections.length; 
    if (len < n - 1) return - 1;
    const uf = new UnionFind(n)
    connections.forEach(([x,y]) =>{
      uf.connect(x,y)
    })
    const ufSize = uf.sizes
    return ufSize-1
  };

  class UnionFind {
    constructor(sizes) {
      this.father = Array.from({ length: sizes }).map((_, index) => index);
      this.sizes = sizes
    }

    find(x) {
      if (x !== this.father[x]) {
        this.father[x] = this.find(this.father[x]);
      }
      return this.father[x];
    }
    connect(x,y){
        let cx = this.find(x)
        let cy = this.find(y)
        if(cx === cy) return 
        this.father[cx] = cy
        this.sizes-- 
    }
  }

[ChenJingjing85]

class Solution:
    '''
    全部电脑形成了n个连通域，就是还需要（n-1）次链接
    在union节点的时候，多余出了几条线，就是最多可以用的线
    '''

    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        def find(x):
            while x != roots[x]:
                roots[x] = roots[roots[x]] #roots[x] 直接等于自己的爷爷
                x = roots[x] #x直接跳到x的爷爷
            return x

        def union(x, y):
            roots[find(x)] = find(y)

        roots = [i for i in range(n)] #roo[i] 表示节点i的root，初始化所有节点的root是自己[0,1,...n-1]
        unnecessary = 0
        for ab in connections:
            a,b = ab
            if find(a) != find(b):
                union(a, b)
            else:
                unnecessary += 1 #find(a) == find(b):说明a,b在之前已经连通，a,b之间的连线是多余的

        root_set = set()
        for i in range(n):
            root_set.add(find(i)) #set 自动去重，保留roots

        return len(root_set)-1 if unnecessary >= (len(root_set)-1) else -1 #多余的线要大于需要的线

• 时间 O（N）
• 空间 O（N） *时间 O（）

[user1689]

题目

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

思路

unionFind

python3

class union_find:

    def __init__(self, size):
        self.father = [None]*size
        self.size = size

    def find(self, x):
        if self.father[x] is None:
            return x
        self.father[x] = self.find(self.father[x])
        return self.father[x]

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

    def merge(self, x, y):
        xx, yy = self.find(x), self.find(y)
        if xx != yy:
            self.father[xx] = yy
            self.size -= 1

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        # time n
        # space n
        uf = union_find(n)
        if len(connections) < n - 1: return -1
        for i, j in connections:
            if uf.is_connected(i, j):
                continue
            uf.merge(i, j)

        return uf.size - 1

复杂度分析

• time n
• space n

相关题目

1. https://leetcode-cn.com/problems/most-stones-removed-with-same-row-or-column/

[mokrs]

class UnionFind {
private:
    vector<int> parent;
    vector<int> size;
    int n;      

public:
    int count;

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

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

    bool Union(int x, int y) {
        x = Find(x);
        y = Find(y);

        if (x == y) {
            return false;
        }

        if (size[x] < size[y]) {
            swap(x, y);
        }

        parent[y] = x;
        size[x] += size[y];
        --count;

        return true;
    }

    bool Connected(int x, int y) {
        x = Find(x);
        y = Find(y);

        return x == y;
    }
};

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

        UnionFind unionFind(n);
        for (auto& connection : connections) {
            unionFind.Union(connection[0], connection[1]);
        }

        return unionFind.count - 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
}

[muimi]

思路

并查集

代码

class UnionFind {
  int[] parent;
  int[] size;
  int count;
  public UnionFind(int n) {
    parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    size = new int[n];
    Arrays.fill(size, 1);
    count = n;
  }
  public int find(int i) {
    while (i != parent[i]) i = parent[i];
    return i;
  }
  public boolean union(int i, int j) {
    int ri = find(i);
    int rj = find(j);
    if (ri == rj) return true;
    if (size[ri] < size[rj]) {
      // swap(i, j)
      int temp = ri;
      ri = rj;
      rj = temp;
    }
    parent[rj] = ri;
    size[ri] += size[rj];
    count--;
    return true;
  }
  public int size() {
    return count;
  }
}
class Solution {
  public int makeConnected(int n, int[][] connections) {
    if (connections.length < n - 1) return -1;
    UnionFind uf = new UnionFind(n);
    for (int[] con : connections) {
      uf.union(con[0], con[1]);
    }
    return uf.size() - 1;
  }
}

[Toms-BigData]

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

[mannnn6]

代码

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.setCount - 1;
    }
}

class UnionFind {
    int[] parent;
    int[] size;
    int n;
    int setCount;

    public UnionFind(int n) {
        this.n = n;
        this.setCount = n;
        this.parent = new int[n];
        this.size = new int[n];
        Arrays.fill(size, 1);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

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

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

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

复杂度

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

[yibenxiao]

【Day 78】1319. 连通网络的操作次数

代码

class UnionFind {
public:
    vector<int> parent;
    vector<int> size;
    int n;
    int setCount;

    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;
    }
};

复杂度

时间复杂度：O(N)

空间复杂度：O(N)

[chaggle]

---

title: "Day 78 1319. 连通网络的操作次数" date: 2021-11-26T22:47:27+08:00 tag: [""] categories: [""] draft: true

---

1319. 连通网络的操作次数

题目

用以太网线缆将 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]
没有重复的连接。
两台计算机不会通过多条线缆连接。

题目思路

• 1、昨日说法

class Djset {
private:
    vector<int> parent;  // 记录节点的根
    vector<int> rank;  // 记录根节点的深度（用于优化）
    int count;         // 记录连通分量的个数
    int rest;          // 记录多余的连接数
public:
    Djset(int n): parent(vector<int>(n)), rank(vector<int>(n)), count(n), rest(0) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        // 压缩方式：直接指向根节点
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void merge(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            // 按秩合并
            if (rank[rootx] < rank[rooty]) {
                swap(rootx, rooty);
            }
            parent[rooty] = rootx;
            if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
            count--;
        } else {
            rest++;
        }
    }
    int getCount() {
        return count;
    }
    int getRest() {
        return rest;
    }
};

class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        Djset ds(n);
        for (auto& e :connections) {
            ds.merge(e[0], e[1]);
        }
        if (ds.getRest() < ds.getCount() - 1) return -1;
        return ds.getCount() - 1;
    }
};

复杂度

• 时间复杂度：O($n^2$)
• 空间复杂度：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

[liuajingliu]

解题思路

并查集

代码实现

var makeConnected = function(n, connections) {
    if (connections.length < n - 1) {
        return -1;
    }

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

    return uf.setCount - 1;
};

class UnionFind {
    constructor (n) {
        this.parent = new Array(n).fill(0).map((element, index) => index);
        this.size = new Array(n).fill(1);
        this.setCount = n;
    }

    findset (x) {
        if (this.parent[x] === x) {
            return x;
        }
        this.parent[x] = this.findset(this.parent[x]);
        return this.parent[x];
    }

    unite (a, b) {
        let x = this.findset(a), y = this.findset(b);
        if (x === y) {
            return false;
        }
        if (this.size[x] < this.size[y]) {
            [x, y] = [y, x];
        }
        this.parent[y] = x;
        this.size[x] += this.size[y];
        this.setCount -= 1;
        return true;
    }

    connected (a, b) {
        const x = this.findset(a), y = this.findset(b);
        return x === y;
    }
}

复杂度分析

• 时间复杂度：$O(m⋅α(n)$, 其中 m 是数组connections的长度，a 是阿克曼函数的反函数
• 空间复杂度: $O(n)$

[Bochengwan]

思路

并查集

代码

    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(connections)，其中 N 为数组长度。
• 空间复杂度：O(n)

[revisegoal]

Write up

连通问题联系并查集，很容易看出连通网络至少需要n-1根线，所以如果少于n-1根线直接返回-1，若满足连通要求且剩下m台电脑没连通网络， 则只需将多余的m条线连上剩下的m台电脑即可，因此，使用并查集求出连通集数-1就得到m，即最少操作次数

Code

class Solution {
    class UF {
        int[] size;
        int[] parent;
        int count;

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

        void union(int p, int q) {
            if (find(p) == find(q)) {
                return;
            }
            if (size[p] < size[q]) {
                parent[find(p)] = find(q);
                size[find(q)]++;
            } else {
                parent[find(q)] = find(p);
                size[find(p)]++;
            }
            count--;
        }

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

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

    }
    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++) {
            uf.union(connections[i][0], connections[i][1]);
        }

        return uf.count - 1;
    }
}

Complexity

• time：接近O(1)
• space：O(n)

[joriscai]

思路

• 并查集

代码

javascript

/*
 * @lc app=leetcode.cn id=1319 lang=javascript
 *
 * [1319] 连通网络的操作次数
 */

// @lc code=start
/**
 * @param {number} n
 * @param {number[][]} connections
 * @return {number}
 */
var makeConnected = function(n, connections) {
  // 连接 n 台电脑至少需要 n - 1 根线缆
  if (connections.length < n - 1) {
    return -1;
  }
  // 计算联通分量，最小操作次数就是将联通分量链接的次数
  let father = Array.from({ length: n }, (v, i) => i);
  let count = n;
  for (connection of connections) {
    union(...connection);
  }

  return count - 1;

  function find(v) {
    if (father[v] !== v) {
      father[v] = find(father[v]);
    }
    return father[v];
  }

  function union(x, y) {
    if (find(x) !== find(y)) {
      count--;
      father[find(x)] = find(y);
      // 联通分量数减一
    }
  }
};
// @lc code=end

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

[brainlds]

class Solution { public int makeConnected(int n, int[][] connections) { UFS ufs = new UFS(n); for(int i = 0 ;i < connections.length;i++){ ufs.union(connections[i][0],connections[i][1]); } int rest = ufs.getrest(),count = ufs.getcount(); if(rest+1 < count) return -1; return count-1; } class UFS{ int[] p; int[] sz; int count; int rest=0; UFS(int n){ count =n; p = new int[n]; sz = new int[n]; for(int i = 0 ; i < n;i++){ p[i] = i; sz[i] = 1; }
}

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

    public void union(int x,int y ){

        int xr = find(x);
        int yr = find(y);
        if(xr != yr){
            p[xr] = yr;
            sz[yr] += sz[xr];
            count--;
        }else{
            rest++;
        }
    }

    public int  size(int x){
        return sz[find(x)];
    }

    public int getrest(){
        return rest;
    }

    public int getcount(){
        return count;
    }

}

}

[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)

Code:

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;
    }

}

[ZETAVI]

class Solution {
    public int makeConnected(int n, int[][] connections) {
        if(connections.length < n-1) return -1;
        int count = n;
        int[] checkAndSet = new int[n];
        for(int i = 0;i < n;i++) checkAndSet[i] = i;
        for(int[] con : connections){
            int index1 = con[0];
            int index2 = con[1];
            if(find(checkAndSet,index1) != find(checkAndSet,index2)){
                union(checkAndSet,index1,index2);
                --count;
            }
        }
        return count-1;
    }

    public void union(int[] checkAndSet,int index1,int index2){
        checkAndSet[find(checkAndSet,index1)] = find(checkAndSet,index2);
    }

    public int find(int[] checkAndSet,int index){
        if(checkAndSet[index] != index) checkAndSet[index] = find(checkAndSet,checkAndSet[checkAndSet[index]]);
        return checkAndSet[index];
    }
}

[BpointA]

思路

并查集（总算摸到点门道）

Python

class unionset:
    def __init__(self,n):
        self.parent=list(range(n))
        self.size=[1]*n
        self.cnt=n
        self.rest=0
    def find(self,x):
        if x!=self.parent[x]:
            self.parent[x]=self.find(self.parent[x])
        return self.parent[x]
    def merge(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x!=y:
            if self.size[x]<self.size[y]:
                x,y=y,x
            self.parent[y]=x
            self.size[x]+=self.size[y]
            self.cnt-=1
        else:
            self.rest+=1

    def getcnt(self):
        return self.cnt
    def getrest(self):
        return self.rest

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        us=unionset(n)
        for i,j  in connections:
            us.merge(i,j)

        if us.getrest()<us.getcnt()-1:
            return -1
        return us.getcnt()-1

[Bingbinxu]

方法 并查集 代码

实现语言: C++
class Solution {
    vector<int> p;    
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        if (connections.size() < n - 1)
            return -1;
        p.resize(n);
        iota(p.begin(), p.end(), 0); // 依次填充0 ~ n-1
        for (const auto& c : connections)
            p[find(c[0])] = find(c[1]);

        unordered_set<int> st;
        for (int i = 0; i < n; i++)
            st.insert(find(i));

        return st.size() - 1;
    }
    int find(int x)
    {
        if (p[x] == x) return x;
        p[x] = find(p[x]);
        return p[x];
    };    
};

复杂度分析 时间复杂度：O(V+E), 其中 V是顶点数, E是边数 空间复杂度：O(V)

[jaysonss]

思路

计算多余的线数量a，和所有的分组数量b, a>=b代表成功返回b，否则返回-1

class Solution {
    Map<Integer,Integer> parents = new HashMap<>();
    int count = 0;
    int dumpCount = 0;

    public int makeConnected(int n, int[][] connections) {
        count = n;
        for(int i=0;i<n;i++){
            parents.put(i,i);
        }

        for(int i=0;i<connections.length;i++){
            int[] conn = connections[i];
            union(conn[0],conn[1]);
        }
        if(dumpCount<count - 1)return -1;
        return count - 1;
    }

    int find(int x){
        if(parents.get(x) == x)return x;
        int root = find(parents.get(x));
        parents.put(x, root);
        return root;
    }

    void union(int x, int y){
        int xp = find(x);
        int yp = find(y);

        if(xp == yp){
            if(x != y){
                dumpCount++;
            }
            return;
        }
        count--;
        parents.put(xp,yp);
        parents.put(x,yp);
    }

}

[chakochako]

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n
        self.n = n
        # 当前连通分量数目
        self.setCount = n

    def findset(self, x: int) -> int:
        if self.parent[x] == x:
            return x
        self.parent[x] = self.findset(self.parent[x])
        return self.parent[x]

    def unite(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(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 connected(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        return x == 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.unite(x, y)

        return uf.setCount - 1

[ginnydyy]

Problem

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

Note

• DFS
  • details: scan the connections, and organize the connections in an array of list with bidirectional connections
• Union find
  • details: write an UnionFind class, union nodes is to union the nodes' parents. When deciding the new parent, consider the nodes' weights. And using pruning when finding the parent of a node

Solution

• DFS

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

        boolean[] visited = new boolean[n];
        List<Integer>[] map = new List[n];
        for(int i = 0; i < n; i++){
            map[i] = new ArrayList<>();
        }

        for(int i = 0; i < edges; i++){
            map[connections[i][0]].add(connections[i][1]);
            map[connections[i][1]].add(connections[i][0]); // note that must add the connection for both ends
        }

        int count = 0;
        for(int i = 0; i < n; i++){
            if(!visited[i]){
                System.out.println("i: " + i);
                visited[i] = true;
                count++;
                dfs(map, i, visited);
            }
        }

        return count - 1;
    }

    private void dfs(List<Integer>[] map, int index, boolean[] visited){
        for(int i: map[index]){
            if(!visited[i]){
                visited[i] = true;
                dfs(map, i, visited);
            }
        }
    }
}

• Union Find

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

public class UnionFind{ public int n; public int setCount; public int[] parent; public int[] size;

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

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

public void union(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y){
        return;
    }

    if(size[x] < size[y]){
        int temp = x;
        x = y;
        y = temp;
    }

    parent[y] = find(x);
    size[x] += size[y];
    setCount--;
}

}

## Complexity
- DFS
  - T: O(n).
  - S: O(n).

- Union Find
  - T: O(m * @(n)). m is the length of connections, @() is the reverse Ackerman function.
  - S: O(n). Extra space is required for the Union Find class.

[hellowxwworld]

思路

并查集

代码

class Solution {
    int ufsFind(vector<int>& ufs, int x) {
        if (ufs[x] < 0)
            return x;
        ufs[x] = ufsFind(ufs, ufs[x]);
        return ufs[x];
    }

    int ufsUnion(vector<int>& ufs, int x, int y) {
        int rx = ufsFind(ufs, x);
        int ry = ufsFind(ufs, y);
        if (rx == ry)
            return -1;
        ufs[rx] += ufs[ry];
        ufs[ry] = rx;
        return ufs[rx];
    }

    int ufsSize(vector<int>& ufs, int x) {
        int rx = ufsFind(ufs, x);
        return -ufs[rx];
    }

    int makeConnected(vector<vector<int>>& connections, int n) {
        int res = 0;
        int m = connections.size();
        if (m + 1 < n)
            return -1;
        vector<int> ufs(n, -1);
        for (int i = 0; i < connections.size(); ++i) {
            ufsUnion(ufs, connections[i][0], connections[i][1]);
        }
        unordered_map<int,int> kvp;
        for (int i = 0; i < n; ++i) {
            if (ufs[i] <= -1)
                ++res;
        }
        res--;
        return res;
    }
};