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

[Ryanbaiyansong]

class UF:
    def __init__(self, n):
        self.f = list(range(n))
        self.size = [1] * n 
        self.count = n

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

    def union(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if fx == fy: return 
        if self.size[fx] < self.size[fy]:
            fx, fy = fy, fx 
        self.size[fx] += self.size[fy]
        self.f[fy] = fx
        self.count -= 1

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        # n 个电脑
        # 
        if len(connections) < n - 1:
            return -1
        uf = UF(n)
        for x, y in connections:
            uf.union(x, y)
        # print(n)
        # print(uf.count)
        # print(len(connections))
        return uf.count - 1

        # 总共有3条边, 2个连通块 -> 3 - 2 = 1
        # 总共有5条边, 3个连通块, 5 - 3 = 2
        # n个点, 至少需要有n-1条边

[snmyj]

class Solution {
vector<int> fa;
vector<int> rank;
public:
    int findx(int x) {
        return x == fa[x] ? x : fa[x] = findx(fa[x]);
    }
    bool unionmerge(int i, int j) {
        int fx = findx(i), fy = findx(j);
        if (fx == fy)
            return true;
        if (rank[fx] < rank[fy])
            swap(fx, fy);
        fa[fy] = fx;
        rank[fx] += rank[fy];
        return true;
    }
    int makeConnected(int n, vector<vector<int>>& connections) {    
        int cns = connections.size();
        if (n - 1 > cns)
            return -1;
        sort(connections.begin(), connections.end());
        int island = 0;
        fa.resize(n);
        rank.resize(n, 1);
        for (int i = 0; i < n; i++)
        {
            fa[i] = i;
        }
        for (int i = 0; i < cns; i++)
        {
            unionmerge(connections[i][0], connections[i][1]);
        }
        for (int i = 0; i < n; i++)
        {
            if (fa[i] == i)
                ++island;
        }
        return island - 1;
    }
};

[zjsuper]

class Solution: def makeConnected(self, n: int, connections: List[List[int]]) -> int: if len(connections)<n-1: return -1 visited = [] dic = {i:[] for i in range(n)} for con in connections: dic[con[0]].append(con[1]) dic[con[1]].append(con[0]) count = 0 for i in range(n): if i not in visited: count +=1 sets = [i] visited.append(i) while sets: k = sets.pop() if dic[k]: for j in dic[k]: if j not in visited: sets.append(j) visited.append(j) return count -1

[bookyue]

thought
做完之后发现官方题解的方法直接返回 连通分量-1，没有多余的判断。
非常好奇为什么可以这样做，他的数学推导应该不成立才对。
然后就看到了两条题目限制条件，原来推导是建立在这上面的啊。

• There are no repeated connections.
• No two computers are connected by more than one cable.

code

    private int[] parent;
    private int[] rank;
    private int count;
    public int makeConnected(int n, int[][] connections) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }

        int cables = 0;
        for (int[] connection : connections) {
            if (!union(connection[0], connection[1]))
                cables++;
        }

        count--;
        return cables < count ? -1 : count;
    }

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

    private boolean union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot) return false;

        if (rank[pRoot] >= rank[qRoot])
            parent[qRoot] = parent[pRoot];
        else
            parent[pRoot] = parent[qRoot];

        if (rank[pRoot] == rank[qRoot])
            rank[pRoot]++;

        count--;
        return true;
    }

[Abby-xu]

class Solution: def makeConnected(self, n: int, connections: List[List[int]]) -> int: par = {i: i for i in range(n)} rank = {i: 1 for i in range(n)}

    def find(n1):
        while n1 != par[n1]:
            par[n1] = par[par[n1]]
            n1 = par[n1]
        return n1

    def union(n1, n2):
        p1, p2 = find(n1), find(n2)
        if p1 == p2:
            return 0
        if rank[p1] < rank[p2]:
            p1, p2 = p2, p1
        par[p2] = p1
        rank[p1] += rank[p2]
        return 1

    # redundant connections
    redun = sum(1 for i, j in connections if not union(i, j))

    # number of connected components
    comp = sum(1 for i in range(n) if find(i) == i)

    return comp - 1 if redun >= comp - 1 else -1

[bwspsu]

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

[FlipN9]

/**
    DSU     TC: O(M*α(N))   SC: O(N)
*/
class Solution {
    public int makeConnected(int N, int[][] connections) {
        int M = connections.length;
        if (M < N - 1) return -1;

        DSU dsu = new DSU(N);
        int count = N - 1;
        for (int[] c : connections) {
            if (dsu.union(c[0], c[1]))
                count--;
        }
        return count;
    }

    class DSU {
        int[] parent;
        int[] rank;

        public DSU(int N) {
            parent = new int[N];
            rank = new int[N];
            Arrays.setAll(parent, r->r);
        }

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

        public boolean union(int a, int b) {
            int pa = find(a);
            int pb = find(b);
            if (pa == pb) return false;
            if (rank[pa] < rank[pb]) {
                parent[pa] = pb;
            } else if (rank[pa] > rank[pb]) {
                parent[pb] = pa;
            } else {
                parent[pb] = pa;
                rank[pa]++;
            }
            return true;
        }
    }
}

[Dou-Yu-xuan]

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

        edges = collections.defaultdict(list)  
        for x, y in connections:  
            edges[x].append(y)  
            edges[y].append(x)  

        seen = set()  

        def dfs(u: int):   
             seen.add(u)  
             for v in edges[u]:  
                if v not in seen:
                    dfs(v)  

        ans = 0   
        for i in range(n):  
            if i not in seen:  
                dfs(i)  
                ans += 1  

        return ans - 1  

[zywang0]

class Solution {
vector<int> fa;
vector<int> rank;
public:
    int findx(int x) {
        return x == fa[x] ? x : fa[x] = findx(fa[x]);
    }
    bool unionmerge(int i, int j) {
        int fx = findx(i), fy = findx(j);
        if (fx == fy)
            return true;
        if (rank[fx] < rank[fy])
            swap(fx, fy);
        fa[fy] = fx;
        rank[fx] += rank[fy];
        return true;
    }
    int makeConnected(int n, vector<vector<int>>& connections) {    
        int cns = connections.size();
        if (n - 1 > cns)
            return -1;
        sort(connections.begin(), connections.end());
        int island = 0;
        fa.resize(n);
        rank.resize(n, 1);
        for (int i = 0; i < n; i++)
        {
            fa[i] = i;
        }
        for (int i = 0; i < cns; i++)
        {
            unionmerge(connections[i][0], connections[i][1]);
        }
        for (int i = 0; i < n; i++)
        {
            if (fa[i] == i)
                ++island;
        }
        return island - 1;
    }
};

[yuexi001]

class Solution {
private:
    vector<vector<int>> edges;
    vector<int> used;

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

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

        edges.resize(n);
        for (const auto& conn: connections) {
            edges[conn[0]].push_back(conn[1]);
            edges[conn[1]].push_back(conn[0]);
        }

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

        return ans - 1;
    }
};

[A-pricity]

/**
 * @param {number} n
 * @param {number[][]} connections
 * @return {number}
 */
class UnionFind {
  constructor(n) {
    this.parents = [];
    for (let i = 0; i < n; i++) {
      this.parents[i] = i;
    }
  }
  find(x) {
    if (x === this.parents[x]) return x;
    const root = this.find(this.parents[x]);
    this.parents[x] = root;
    return root;
  }
  union(x, y) {
    const x_ = this.find(x);
    const y_ = this.find(y);
    if (x_ === y_) return 0;
    this.parents[x_] = y_;
    return 1;
  }
}

/**
 * @param {number} n
 * @param {number[][]} connections
 * @return {number}
 */
var makeConnected = function (n, connections) {
  if(connections.length < n - 1) return -1
  const u = new UnionFind(n)
  for(const [x, y] of connections) u.union(x, y)

  let ans = -1
  for(let i = 0; i < n; i++){
    if(u.parents[i] === i) ans++
  }
  return ans
};

[klspta]

class Solution {
    private int[] p;
    private int find(int x){
        if(p[x] != x){
            return find(p[x]);
        }
        return p[x];
    }
    public int makeConnected(int n, int[][] connections) {
        if(connections.length < n - 1){
            return -1;
        }
        p = new int[n];
        for(int i = 0; i < n; i++){
            p[i] = i;
        }
        int res = n;
        for(int[] connection : connections){
            int a = connection[0];
            int b = connection[1];
            if(find(a) != find(b)){
                p[find(a)] = find(b);
                res--;
            }
        }
        return res - 1;
    }
}

[paopaohua]

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

[Elsa-zhang]

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) :
        if self.parent[x] == x:
            return x
        self.parent[x] = self.findset(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int):
        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

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:

        uf = UnionFind(n)

        if len(connections)<n-1:
            return -1

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

        return uf.setCount - 1

[Elon-Lau]

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) :
    if self.parent[x] == x:
        return x
    self.parent[x] = self.findset(self.parent[x])
    return self.parent[x]

def union(self, x: int, y: int):
    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

class Solution: def makeConnected(self, n: int, connections: List[List[int]]) -> int:

    uf = UnionFind(n)

    if len(connections)<n-1:
        return -1

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

    return uf.setCount - 1
```

[saitoChen]

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

    const edges = new Map();
    for (const [x, y] of connections) {
        edges.get(x) ? edges.get(x).push(y) : edges.set(x, [y]);
        edges.get(y) ? edges.get(y).push(x) : edges.set(y, [x]);
    }

    const used = new Array(n).fill(0);

    let ans = 0;
    for (let i = 0; i < n; i++) {
        if (!used[i]) {
            dfs(i, used, edges);
            ans++;
        }
    }
    return ans - 1;
};

const dfs = (u, used, edges) => {
    used[u] = 1;
    if (edges.get(u)) {
        for (const v of edges.get(u)) {
            if (!used[v]) {
                dfs(v, used, edges);
            }
        }
    }
}

[tiandao043]

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

        vector<int> fa(n);
        iota(fa.begin(), fa.end(), 0);     //从0开始自增初始化

        function<int(int)> findset = [&](int x) {return x == fa[x] ? x : fa[x] = findset(fa[x]);};
        //通过std::function对C++中各种可调用实体（普通函数、Lambda表达式、函数指针、仿函数以及其它函数对象等）的封装，形成一个新的可调用的、统一的std::function对象。

        int part = n;
        for (auto&& c: connections) {
            int p = findset(c[0]), q = findset(c[1]);
            if (p != q) {
                --part;
                fa[p] = q;
            }
        }

        return part - 1;
    }
};

[whoam-challenge]

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

    edges = collections.defaultdict(list)
    for x, y in connections:
        edges[x].append(y)
        edges[y].append(x)

    seen = set()

    def dfs(u: int):
        seen.add(u)
        for v in edges[u]:
            if v not in seen:
                dfs(v)

    ans = 0
    for i in range(n):
        if i not in seen:
            dfs(i)
            ans += 1

    return ans - 1

[Jetery]

const int N = 1e5 + 10;
class Solution {
public:
    int count, a[N];

    void init(int n) {
        count = n;
        for (int i = 0; i < n; i++) a[i] = i;
    }

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

    bool unio(int i, int j) {
        int x = find(i), y = find(j);
        if (x == y) return false;
        a[x] = y;
        count--;
        return true;
    }

    int makeConnected(int n, vector<vector<int>>& connections) {
        init(n);
        int cable = 0;
        for (vector<int> temp : connections) {
            int i = temp[0], j = temp[1];
            if (!unio(i, j)) cable++;
        }
        count--; // 需要用于连接的线为总个数 - 1
        return cable < count ? -1 : count;
    }
};

[mayloveless]

思路

线最少需要n-1根，找出不连通的有几堆，减去1就是需要补充的线的根数，即移动根数

代码

/**
 * @param {number} n
 * @param {number[][]} connections
 * @return {number}
 */
var makeConnected = function(n, connections) {
    // 线不够
    if (connections.length  < n-1) {
        return -1;
    }

    const parent = Array.from({ length: n }, (v, i) => i);
    function find(v) {
        if (parent[v] !== v) {
            parent[v] = find(parent[v]);
        }
        return parent[v];
    }

    function union(x, y) {
        const xset = find(x);
        const yset = find( y);
        if (xset != yset) {
            parent[xset] = yset;// x指向y
            res--;
        }
    }

    var res = n;
    for (const connection of connections) {
        union(...connection);
    }

   // 块-1为需要的补充的线，即移动的线
   return  res -1;
};

复杂度

时间：O（logx）并查集查找的次数 空间：O(n)并查集需要使用的空间

[RestlessBreeze]

code

class Solution {
private:
    vector<vector<int>> edges;
    vector<int> used;

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

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

        edges.resize(n);
        for (const auto& conn: connections) {
            edges[conn[0]].push_back(conn[1]);
            edges[conn[1]].push_back(conn[0]);
        }

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

        return ans - 1;
    }
};