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

[lp1506947671]

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

复杂度分析

令 v 图的点的个数，也就是计算机的个数。

• 时间复杂度：由于仅仅使用了路径压缩，因此合并与查找时间复杂度为 O(logx)和 O(logy)，x 和 y 分别为合并与查找的次数。
• 空间复杂度：O(v)。

[RestlessBreeze]

code

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

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

    void Union(int index1, int index2)
    {
        int parent1 = find(index1);
        int parent2 = find(index2);

        if (parent1 == parent2)
            return;
        else
        {
            if (weight[parent1] <= weight[parent2])
            {
                parent[parent1] = parent2;
                weight[parent2] += weight[parent1];
                weight[parent1] = 0;
                count--;
            }
            else
            {
                parent[parent2] = parent1;
                weight[parent1] += weight[parent2];
                weight[parent2] = 0;
                count--;
            }
        }
    }
};

class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        UF uf(n);
        for (int i = 0; i < connections.size(); i++)
        {
            int tempx = connections[i][0];
            int tempy = connections[i][1];
            uf.Union(tempx, tempy);
        }

        if (connections.size() < n - 1)
            return -1;
        return uf.count - 1;
    }
};

[bookyue]

TC: O(m) SC: O(m)

    private int[] parent;
    private int[] rank;
    private int count;

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

        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++)
            parent[i] = i;

        for (int[] connection : connections)
            union(connection[0], connection[1]);

        return count - 1;
    }

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

        return p;
    }

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

        if (pRoot == qRoot) return;

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

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

        count--;
    }

[kangliqi1]

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

}

[harperz24]

class UnionFind:
    def __init__(self, n):
        self.root = list(range(n))
        self.rank = [1] * n
        self.set_count = n

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

    def union(self, x: int, y: int):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return
        rank_x, rank_y = self.rank[root_x], self.rank[root_y]
        if rank_x >= rank_y:
            self.root[root_y] = root_x
            rank_up = 1 if rank_x == rank_y else 0
            self.rank[root_x] += rank_up
        else:
            self.root[root_x] = root_y
        self.set_count -= 1

    def connected(self, x: int, y: int) -> bool:
        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.set_count - 1

[sye9286]

代码

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

复杂度分析

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

[snmyj]

class Solution {
public:
    vector<int> p;
    int find(int x){
        if(x!=p[x]) p[x]=find(p[x]);
        return p[x];
    }
    void connect(int a,int b){
        int pa=find(a),pb=find(b);
        p[pa]=pb;
    }
    int makeConnected(int n, vector<vector<int>>& connections) {
     int m=connections.size();
     if(n-1>m) return -1;
     p.resize(n);
     for(int i=0;i<n;i++) p[i]=i;
     for(auto e:connections){
         int a=e[0],b=e[1];
         if(find(a)!=find(b)) {
             connect(a,b);
             --n;
         }
     }
     return n-1;
    }
};

[Diana21170648]

思路

并查集或dfs都能做

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

**复杂度分析**
- 时间复杂度：T=O(logx)+O（logy），使用了路径压缩
- 空间复杂度：S=O(n)，网络中的节点个数

[FireHaoSky]

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

[linlizzz]

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

[Fuku-L]

代码

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;
    }
    private void dfs(int u){
        used[u] = true;
        for(int v : edges[u]){
            if(!used[v]){
                dfs(v);
            }
        }
    }
}

复杂度分析

• 时间复杂度：O(N+M)，其中 M 为数组connections长度。
• 空间复杂度：O(N+M)，其中 O(M) 为存储所有边需要的空间，O(N)为dfs中使用栈空间。

[chocolate-emperor]

class Solution {
public:
    int pa[100000+4];
    int findparent(int x){
        if(pa[x]==x)    return pa[x];
        int root = findparent(pa[x]);
        pa[x] = root;
        return pa[x];
    }
    void SetUnion(int x,int y){
        int roota = findparent(x);
        int rootb = findparent(y);
        if(roota!=rootb){
            pa[rootb] = roota;
        }
    }
    int makeConnected(int n, vector<vector<int>>& connections) {
        for(int i = 0; i<n;i++){
            pa[i] = i;
        }

        int remains = 0;
        for(auto edge: connections){
            if(findparent(edge[0])==findparent(edge[1])) {
                remains+=1;
                continue;
            }else{
                SetUnion(edge[0],edge[1]);
            }
        }
        int cnt_center=0;
        unordered_set<int>roots;
        for(int i = 0; i<n;i++){
            roots.insert(findparent(i));
        }
        if(remains< roots.size()-1) return -1;
        return roots.size()-1;
    }
};

[X1AOX1A]

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

[JasonQiu]

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1:
            return -1
        graph = defaultdict(list)
        visited = set()
        count = 0

        for c in connections:
            graph[c[0]].append(c[1])
            graph[c[1]].append(c[0])

        def dfs(current):
            for next_node in graph[current]:
                if next_node not in visited:
                    visited.add(next_node)
                    dfs(next_node)

        for node in range(n):
            if node not in visited:
                visited.add(node)
                dfs(node)
                count += 1

        return count - 1

Time: O(V+E) Space: O(V+E)

[joemonkeylee]

思路

并查集

代码

    class UnionFind {
        private parents: Array<number>
        private sizes: Array<number>
        private extraCables: number
        private numOfSets: number

        constructor(size: number) {
            this.parents = Array(size)
                .fill(0)
                .map((_, i) => i)
            this.sizes = Array(size).fill(1)
            this.extraCables = 0
            this.numOfSets = size
        }

        size(): number {
            return this.numOfSets
        }

        getExtraCables(): number {
            return this.extraCables
        }

        findSet(x: number): number {
            if (x !== this.parents[x]) {
                this.parents[x] = this.findSet(this.parents[x])
            }
            return this.parents[x]
        }

        unionSet(x: number, y: number): void {
            const px: number = this.findSet(x)
            const py: number = this.findSet(y)
            if (px === py) {
                this.extraCables++
                return
            }
            if (this.sizes[px] > this.sizes[py]) {
                this.parents[py] = px
                this.sizes[px] += this.sizes[py]
            } else {
                this.parents[px] = py
                this.sizes[py] += this.sizes[px]
            }
            this.numOfSets--
        }
    }

    function makeConnected(n: number, connections: number[][]): number {
        const uf: UnionFind = new UnionFind(n)
        for (let c of connections) {
            uf.unionSet(c[0], c[1])
        }
        return uf.getExtraCables() >= uf.size() - 1 ? uf.size() - 1 : -1
    };

复杂度分析

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

[Lydia61]

1319. 联通网络的操作次数

思路

查并集

代码

class Solution {
    vector<int> ps; // 保存并查集的每个i的根
    //并查集的查操作
    int find(int x) {
        if (x != ps[x]) ps[x] = find(ps[x]); //压缩路径的写法
        return ps[x];
    }
    //并查集的并操作
    void connect(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        ps[pa] = pb;
    }
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        int m = connections.size();
        if (n > m + 1) return -1; //如果要连通n个点 至少要n - 1条边
        ps.resize(n);
        //iota 初始化查并集
        iota(ps.begin(), ps.end(), 0);
        for (auto &e: connections) {
            int a = e[0], b = e[1];
            if (find(a) != find(b)) {
                connect(a, b);
                --n;   // 每做一次并操作, 图的连通分量减1
            }
        }
        //从当前的n个连通分量到1个连通分量要至少改n - 1条边
        return n - 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;
    }
};

[tzuikuo]

思路

代码

class Solution {
    void dfs(vector<int> adj[], vector<bool> &visited, int src)
    {
        visited[src] = true;
        for(int i : adj[src]){
            if(!visited[i]){
                dfs(adj, visited, i);
            }
        }
    }
public:
    int makeConnected(int n, vector<vector<int>>& arr) {
        int len = arr.size();
        if(len<n-1) return -1;
         vector<int> adj[n];
        for(auto v : arr)
        {
            adj[v[0]].push_back(v[1]);
            adj[v[1]].push_back(v[0]);
        }
        vector<bool> visited(n, false);
        int ans = 0;
        for(int i=0; i<n; i++)
        if(!visited[i])
        {
            dfs(adj, visited, i);
            ans++;
        }
        return ans - 1;
    }
};

复杂度分析 -待定

[kofzhang]

思路

并查集

代码

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections)<n-1:
            return -1
        comps = [-1]*n
        def find(com):
            t = com
            while comps[t]>=0:
                t = comps[t]
            while t!=com:
                comps[com],com=t,comps[com]
            return t

        def union(c1,c2):
            root1 = find(c1)
            root2 = find(c2)
            if root1==root2:
                return
            elif root1<root2:
                comps[root2]=root1
            else:
                comps[root1]=root2

        for i,j in connections:
            union(i,j)

        count = 0
        for i in comps:
            if i==-1:
                count += 1
        return count-1

[chanceyliu]

代码

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

function makeConnected(n: number, connections: number[][]): number {
  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;
};