leetcode1319. 连通网络的操作次数（并查集）_java 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 上。

代码

class Solution {
    int[] fa;//并查集操作
    public void  init()
    {
        for(int i=0;i<fa.length;i++)
            fa[i]=i;

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

    }
    public int makeConnected(int n, int[][] connections) {

        int rest=0,cnt=-1;
        fa=new int[n];
        init();
        for(int[] c:connections)
        {
            if(find(c[0])==find(c[1]))//找出多余的线
                rest++;
            else union(c[0],c[1]);
        }
        for(int i=0;i<n;i++)//找出没有连接的电脑
            if(fa[i]==i) cnt++;
            if(rest<cnt) return -1;//线的数量不够
            return cnt;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39