Skip to content

Commit 1f12d3c

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1319
No.1319.Number of Operations to Make Network Connected
1 parent 5be4309 commit 1f12d3c

File tree

6 files changed

+102
-169
lines changed

6 files changed

+102
-169
lines changed

‎solution/1300-1399/1319.Number of Operations to Make Network Connected/README.md

Lines changed: 34 additions & 57 deletions
Original file line numberDiff line numberDiff line change
@@ -135,21 +135,20 @@ d[find(a)] = distance
135135
```python
136136
class Solution:
137137
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
138-
p = list(range(n))
139-
140138
def find(x):
141139
if p[x] != x:
142140
p[x] = find(p[x])
143141
return p[x]
144142

145-
cnt = 0
143+
cnt, size = 0, n
144+
p = list(range(n))
146145
for a, b in connections:
147146
if find(a) == find(b):
148147
cnt += 1
149148
else:
150149
p[find(a)] = find(b)
151-
total = sum(i == find(i) for i in range(n))
152-
return -1 if total - 1 > cnt else total - 1
150+
size -= 1
151+
return -1 if size - 1 > cnt else size - 1
153152
```
154153

155154
### **Java**
@@ -167,19 +166,16 @@ class Solution {
167166
}
168167
int cnt = 0;
169168
for (int[] e : connections) {
170-
if (find(e[0]) == find(e[1])) {
169+
int a = e[0];
170+
int b = e[1];
171+
if (find(a) == find(b)) {
171172
++cnt;
172173
} else {
173-
p[find(e[0])] = find(e[1]);
174+
p[find(a)] = find(b);
175+
--n;
174176
}
175177
}
176-
int total = 0;
177-
for (int i = 0; i < n; ++i) {
178-
if (i == find(i)) {
179-
++total;
180-
}
181-
}
182-
return total - 1 > cnt ? -1 : total - 1;
178+
return n - 1 > cnt ? -1 : n - 1;
183179
}
184180

185181
private int find(int x) {
@@ -198,38 +194,25 @@ class Solution {
198194
public:
199195
vector<int> p;
200196

201-
int makeConnected(int n, vector<vector<int>> &connections) {
197+
int makeConnected(int n, vector<vector<int>>& connections) {
202198
p.resize(n);
203-
for (int i = 0; i < n; ++i)
204-
{
205-
p[i] = i;
206-
}
199+
for (int i = 0; i < n; ++i) p[i] = i;
207200
int cnt = 0;
208-
for (auto e : connections)
201+
for (auto& e : connections)
209202
{
210-
if (find(e[0]) == find(e[1]))
211-
{
212-
++cnt;
213-
}
203+
int a = e[0], b = e[1];
204+
if (find(a) == find(b)) ++cnt;
214205
else
215206
{
216-
p[find(e[0])] = find(e[1]);
207+
p[find(a)] = find(b);
208+
--n;
217209
}
218210
}
219-
int total = 0;
220-
for (int i = 0; i < n; ++i)
221-
{
222-
if (i == find(i))
223-
{
224-
++total;
225-
}
226-
}
227-
return total - 1 > cnt ? -1 : total - 1;
211+
return n - 1 > cnt ? -1 : n - 1;
228212
}
229213

230214
int find(int x) {
231-
if (p[x] != x)
232-
p[x] = find(p[x]);
215+
if (p[x] != x) p[x] = find(p[x]);
233216
return p[x];
234217
}
235218
};
@@ -238,38 +221,32 @@ public:
238221
### **Go**
239222
240223
```go
241-
var p []int
242-
243224
func makeConnected(n int, connections [][]int) int {
244-
p = make([]int, n)
245-
for i := 0; i < n; i++ {
225+
p := make([]int, n)
226+
for i := range p {
246227
p[i] = i
247228
}
248229
cnt := 0
230+
var find func(x int) int
231+
find = func(x int) int {
232+
if p[x] != x {
233+
p[x] = find(p[x])
234+
}
235+
return p[x]
236+
}
249237
for _, e := range connections {
250-
if find(e[0]) == find(e[1]) {
238+
a, b := e[0], e[1]
239+
if find(a) == find(b) {
251240
cnt++
252241
} else {
253-
p[find(e[0])] = find(e[1])
254-
}
255-
}
256-
total := 0
257-
for i := 0; i < n; i++ {
258-
if i == find(i) {
259-
total++
242+
p[find(a)] = find(b)
243+
n--
260244
}
261245
}
262-
if total-1 > cnt {
246+
if n-1 > cnt {
263247
return -1
264248
}
265-
return total - 1
266-
}
267-
268-
func find(x int) int {
269-
if p[x] != x {
270-
p[x] = find(p[x])
271-
}
272-
return p[x]
249+
return n - 1
273250
}
274251
```
275252

‎solution/1300-1399/1319.Number of Operations to Make Network Connected/README_EN.md

Lines changed: 35 additions & 56 deletions
Original file line numberDiff line numberDiff line change
@@ -58,28 +58,29 @@
5858

5959
## Solutions
6060

61+
Union find.
62+
6163
<!-- tabs:start -->
6264

6365
### **Python3**
6466

6567
```python
6668
class Solution:
6769
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
68-
p = list(range(n))
69-
7070
def find(x):
7171
if p[x] != x:
7272
p[x] = find(p[x])
7373
return p[x]
7474

7575
cnt = 0
76+
p = list(range(n))
7677
for a, b in connections:
7778
if find(a) == find(b):
7879
cnt += 1
7980
else:
8081
p[find(a)] = find(b)
81-
total = sum(i == find(i) for i in range(n))
82-
return -1 if total - 1 > cnt else total - 1
82+
n -= 1
83+
return -1 if n - 1 > cnt else n - 1
8384
```
8485

8586
### **Java**
@@ -95,19 +96,16 @@ class Solution {
9596
}
9697
int cnt = 0;
9798
for (int[] e : connections) {
98-
if (find(e[0]) == find(e[1])) {
99+
int a = e[0];
100+
int b = e[1];
101+
if (find(a) == find(b)) {
99102
++cnt;
100103
} else {
101-
p[find(e[0])] = find(e[1]);
102-
}
103-
}
104-
int total = 0;
105-
for (int i = 0; i < n; ++i) {
106-
if (i == find(i)) {
107-
++total;
104+
p[find(a)] = find(b);
105+
--n;
108106
}
109107
}
110-
return total - 1 > cnt ? -1 : total - 1;
108+
return n - 1 > cnt ? -1 : n - 1;
111109
}
112110

113111
private int find(int x) {
@@ -126,38 +124,25 @@ class Solution {
126124
public:
127125
vector<int> p;
128126

129-
int makeConnected(int n, vector<vector<int>> &connections) {
127+
int makeConnected(int n, vector<vector<int>>& connections) {
130128
p.resize(n);
131-
for (int i = 0; i < n; ++i)
132-
{
133-
p[i] = i;
134-
}
129+
for (int i = 0; i < n; ++i) p[i] = i;
135130
int cnt = 0;
136-
for (auto e : connections)
131+
for (auto& e : connections)
137132
{
138-
if (find(e[0]) == find(e[1]))
139-
{
140-
++cnt;
141-
}
133+
int a = e[0], b = e[1];
134+
if (find(a) == find(b)) ++cnt;
142135
else
143136
{
144-
p[find(e[0])] = find(e[1]);
137+
p[find(a)] = find(b);
138+
--n;
145139
}
146140
}
147-
int total = 0;
148-
for (int i = 0; i < n; ++i)
149-
{
150-
if (i == find(i))
151-
{
152-
++total;
153-
}
154-
}
155-
return total - 1 > cnt ? -1 : total - 1;
141+
return n - 1 > cnt ? -1 : n - 1;
156142
}
157143

158144
int find(int x) {
159-
if (p[x] != x)
160-
p[x] = find(p[x]);
145+
if (p[x] != x) p[x] = find(p[x]);
161146
return p[x];
162147
}
163148
};
@@ -166,38 +151,32 @@ public:
166151
### **Go**
167152
168153
```go
169-
var p []int
170-
171154
func makeConnected(n int, connections [][]int) int {
172-
p = make([]int, n)
173-
for i := 0; i < n; i++ {
155+
p := make([]int, n)
156+
for i := range p {
174157
p[i] = i
175158
}
176159
cnt := 0
160+
var find func(x int) int
161+
find = func(x int) int {
162+
if p[x] != x {
163+
p[x] = find(p[x])
164+
}
165+
return p[x]
166+
}
177167
for _, e := range connections {
178-
if find(e[0]) == find(e[1]) {
168+
a, b := e[0], e[1]
169+
if find(a) == find(b) {
179170
cnt++
180171
} else {
181-
p[find(e[0])] = find(e[1])
182-
}
183-
}
184-
total := 0
185-
for i := 0; i < n; i++ {
186-
if i == find(i) {
187-
total++
172+
p[find(a)] = find(b)
173+
n--
188174
}
189175
}
190-
if total-1 > cnt {
176+
if n-1 > cnt {
191177
return -1
192178
}
193-
return total - 1
194-
}
195-
196-
func find(x int) int {
197-
if p[x] != x {
198-
p[x] = find(p[x])
199-
}
200-
return p[x]
179+
return n - 1
201180
}
202181
```
203182

‎solution/1300-1399/1319.Number of Operations to Make Network Connected/Solution.cpp

Lines changed: 9 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -2,38 +2,25 @@ class Solution {
22
public:
33
vector<int> p;
44

5-
int makeConnected(int n, vector<vector<int>> &connections) {
5+
int makeConnected(int n, vector<vector<int>>& connections) {
66
p.resize(n);
7-
for (int i = 0; i < n; ++i)
8-
{
9-
p[i] = i;
10-
}
7+
for (int i = 0; i < n; ++i) p[i] = i;
118
int cnt = 0;
12-
for (auto e : connections)
9+
for (auto& e : connections)
1310
{
14-
if (find(e[0]) == find(e[1]))
15-
{
16-
++cnt;
17-
}
11+
int a = e[0], b = e[1];
12+
if (find(a) == find(b)) ++cnt;
1813
else
1914
{
20-
p[find(e[0])] = find(e[1]);
21-
}
22-
}
23-
int total = 0;
24-
for (int i = 0; i < n; ++i)
25-
{
26-
if (i == find(i))
27-
{
28-
++total;
15+
p[find(a)] = find(b);
16+
--n;
2917
}
3018
}
31-
return total - 1 > cnt ? -1 : total - 1;
19+
return n - 1 > cnt ? -1 : n - 1;
3220
}
3321

3422
int find(int x) {
35-
if (p[x] != x)
36-
p[x] = find(p[x]);
23+
if (p[x] != x) p[x] = find(p[x]);
3724
return p[x];
3825
}
3926
};

0 commit comments

Comments
 (0)