LeetCode1319:连通网络的操作次数_连通网络的操作次数python

分析：线的数量就是connections的值，而连接n台计算机至少需要 n - 1条线。判断是否重复连线，只需判断两台计算机是否已经在同一个网络中。如果已经相连，则把线取下。

1.遍历整个connections
2.计算有多少个集合，以及有多少剩余的线
3.集合数量-1即为最少操作次数,与剩余的线的数量进行比较即可

int makeConnected(){
	初始化并查集
			
	for (遍历connections数组) {
		if (connections[i][0] 和connections[i][1]不在同一个集合内) {
			合并这两个元素所在的集合
			线的数量  - 1
			集合数量  -  1
		}
	}
	
	return (线的数量 >= 集合数量 - 1 ？ 集合数量 - 1 : -1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

具体代码：

static int* Initialize(int size){

    int *Set = (int*)malloc(sizeof(int) * size);
    assert(Set);

    for (int i = 0; i < size; ++i)
        Set[i] = 0;
    return Set;
}

//用这种方式初始化时并未注意到Set[i] = 0是非法的，应该是(*Set)[i] = 0.
//所以，尽量避免使用多维指针，使用多维指针时一定要格外警惕。
static void Initialize(int **Set, int size){
	
	(*Set) = (int*)malloc(sizeof(int) * size);
	assert(Set);
	
	for (int i = 0; i < size; ++i)
		(*Set)[i] = 0;
}

static int Find(int *Set, int X){

    if (Set[X] <= 0)
        return X;
    else
        return Set[X] = Find(Set, Set[X]);
}

static void Set_Union(int *Set, int p, int q){

    int proot = Find(Set, p);
    int qroot = Find(Set, q);

    if (Set[proot] < Set[qroot])
        Set[qroot] = proot;
    else {
        if (Set[qroot]  == Set[proot])
            Set[qroot]--;
        Set[proot] = qroot; 
    }
}

inline static bool isConnected(int *Set, int p, int q){
    return (Find(Set, p) == Find(Set, q) ? true : false);
}

int makeConnected(int n, int** connections, int connectionsSize, int* connectionsColSize){

    int *Set = Initialize(n);

    int rest = connectionsSize;
    for (int i = connectionsSize - 1; i >= 0; --i) {
        if (isConnected(Set, connections[i][0], connections[i][1]))
            continue;
        Set_Union(Set, connections[i][0], connections[i][1]);
        --rest;
        --n;
    }

    int opration = n - 1;

    return (opration <= rest ? opration : -1);
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

反思：使用二维指针初始化时未注意到这是二维指针，能使用低维指针尽量使用低维指针。