Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 8f3170e

Browse files
committed
feat: update solutions to lc problem: No.0547.Number of Provinces
1 parent ed71f0f commit 8f3170e

File tree

4 files changed

+54
-72
lines changed

4 files changed

+54
-72
lines changed

‎solution/0500-0599/0547.Number of Provinces/README.md‎

Lines changed: 21 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -145,19 +145,20 @@ class Solution:
145145
```python
146146
class Solution:
147147
def findCircleNum(self, isConnected: List[List[int]]) -> int:
148-
n = len(isConnected)
148+
n = size =len(isConnected)
149149
p = list(range(n))
150150

151151
def find(x):
152152
if p[x] != x:
153153
p[x] = find(p[x])
154154
return p[x]
155-
155+
156156
for i in range(n):
157157
for j in range(n):
158-
if i != j andisConnected[i][j] == 1:
158+
if isConnected[i][j] == 1and find(i) != find(j):
159159
p[find(i)] = find(j)
160-
return sum(i == find(i) for i in range(n))
160+
size -= 1
161+
return size
161162
```
162163

163164
### **Java**
@@ -204,20 +205,16 @@ class Solution {
204205
for (int i = 0; i < n; ++i) {
205206
p[i] = i;
206207
}
208+
int size = n;
207209
for (int i = 0; i < n; ++i) {
208210
for (int j = 0; j < n; ++j) {
209-
if (isConnected[i][j] == 1) {
211+
if (isConnected[i][j] == 1&& find(i) != find(j)) {
210212
p[find(i)] = find(j);
213+
--size;
211214
}
212215
}
213216
}
214-
int cnt = 0;
215-
for (int i = 0; i < n; ++i) {
216-
if (i == find(i)) {
217-
++cnt;
218-
}
219-
}
220-
return cnt;
217+
return size;
221218
}
222219

223220
private int find(int x) {
@@ -240,19 +237,19 @@ public:
240237
int n = isConnected.size();
241238
p.resize(n);
242239
for (int i = 0; i < n; ++i) p[i] = i;
240+
int size = n;
243241
for (int i = 0; i < n; ++i)
244242
{
245243
for (int j = 0; j < n; ++j)
246244
{
247-
if (i != j && isConnected[i][j] == 1) p[find(i)] = find(j);
245+
if (isConnected[i][j] && find(i) != find(j))
246+
{
247+
p[find(i)] = find(j);
248+
--size;
249+
}
248250
}
249251
}
250-
int cnt = 0;
251-
for (int i = 0; i < n; ++i)
252-
{
253-
if (i == find(i)) ++cnt;
254-
}
255-
return cnt;
252+
return size;
256253
}
257254

258255
int find(int x) {
@@ -270,23 +267,19 @@ var p []int
270267
func findCircleNum(isConnected [][]int) int {
271268
n := len(isConnected)
272269
p = make([]int, n)
273-
for i := 1; i < n; i++ {
270+
for i := 0; i < n; i++ {
274271
p[i] = i
275272
}
273+
size := n
276274
for i := 0; i < n; i++ {
277275
for j := 0; j < n; j++ {
278-
if isConnected[i][j] == 1 {
276+
if isConnected[i][j] == 1 && find(i) != find(j) {
279277
p[find(i)] = find(j)
278+
size--
280279
}
281280
}
282281
}
283-
cnt := 0
284-
for i := 0; i < n; i++ {
285-
if i == find(i) {
286-
cnt++
287-
}
288-
}
289-
return cnt
282+
return size
290283
}
291284
292285
func find(x int) int {

‎solution/0500-0599/0547.Number of Provinces/README_EN.md‎

Lines changed: 21 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -67,19 +67,20 @@ class Solution:
6767
```python
6868
class Solution:
6969
def findCircleNum(self, isConnected: List[List[int]]) -> int:
70-
n = len(isConnected)
70+
n = size =len(isConnected)
7171
p = list(range(n))
7272

7373
def find(x):
7474
if p[x] != x:
7575
p[x] = find(p[x])
7676
return p[x]
77-
77+
7878
for i in range(n):
7979
for j in range(n):
80-
if i != j andisConnected[i][j] == 1:
80+
if isConnected[i][j] == 1and find(i) != find(j):
8181
p[find(i)] = find(j)
82-
return sum(i == find(i) for i in range(n))
82+
size -= 1
83+
return size
8384
```
8485

8586
### **Java**
@@ -120,20 +121,16 @@ class Solution {
120121
for (int i = 0; i < n; ++i) {
121122
p[i] = i;
122123
}
124+
int size = n;
123125
for (int i = 0; i < n; ++i) {
124126
for (int j = 0; j < n; ++j) {
125-
if (isConnected[i][j] == 1) {
127+
if (isConnected[i][j] == 1&& find(i) != find(j)) {
126128
p[find(i)] = find(j);
129+
--size;
127130
}
128131
}
129132
}
130-
int cnt = 0;
131-
for (int i = 0; i < n; ++i) {
132-
if (i == find(i)) {
133-
++cnt;
134-
}
135-
}
136-
return cnt;
133+
return size;
137134
}
138135

139136
private int find(int x) {
@@ -156,19 +153,19 @@ public:
156153
int n = isConnected.size();
157154
p.resize(n);
158155
for (int i = 0; i < n; ++i) p[i] = i;
156+
int size = n;
159157
for (int i = 0; i < n; ++i)
160158
{
161159
for (int j = 0; j < n; ++j)
162160
{
163-
if (i != j && isConnected[i][j] == 1) p[find(i)] = find(j);
161+
if (isConnected[i][j] && find(i) != find(j))
162+
{
163+
p[find(i)] = find(j);
164+
--size;
165+
}
164166
}
165167
}
166-
int cnt = 0;
167-
for (int i = 0; i < n; ++i)
168-
{
169-
if (i == find(i)) ++cnt;
170-
}
171-
return cnt;
168+
return size;
172169
}
173170

174171
int find(int x) {
@@ -186,23 +183,19 @@ var p []int
186183
func findCircleNum(isConnected [][]int) int {
187184
n := len(isConnected)
188185
p = make([]int, n)
189-
for i := 1; i < n; i++ {
186+
for i := 0; i < n; i++ {
190187
p[i] = i
191188
}
189+
size := n
192190
for i := 0; i < n; i++ {
193191
for j := 0; j < n; j++ {
194-
if isConnected[i][j] == 1 {
192+
if isConnected[i][j] == 1 && find(i) != find(j) {
195193
p[find(i)] = find(j)
194+
size--
196195
}
197196
}
198197
}
199-
cnt := 0
200-
for i := 0; i < n; i++ {
201-
if i == find(i) {
202-
cnt++
203-
}
204-
}
205-
return cnt
198+
return size
206199
}
207200
208201
func find(x int) int {

‎solution/0500-0599/0547.Number of Provinces/Solution.cpp‎

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -6,19 +6,19 @@ class Solution {
66
int n = isConnected.size();
77
p.resize(n);
88
for (int i = 0; i < n; ++i) p[i] = i;
9+
int size = n;
910
for (int i = 0; i < n; ++i)
1011
{
1112
for (int j = 0; j < n; ++j)
1213
{
13-
if (i != j && isConnected[i][j] == 1) p[find(i)] = find(j);
14+
if (isConnected[i][j] && find(i) != find(j))
15+
{
16+
p[find(i)] = find(j);
17+
--size;
18+
}
1419
}
1520
}
16-
int cnt = 0;
17-
for (int i = 0; i < n; ++i)
18-
{
19-
if (i == find(i)) ++cnt;
20-
}
21-
return cnt;
21+
return size;
2222
}
2323

2424
int find(int x) {

‎solution/0500-0599/0547.Number of Provinces/Solution.go‎

Lines changed: 5 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -3,23 +3,19 @@ var p []int
33
func findCircleNum(isConnected [][]int) int {
44
n := len(isConnected)
55
p = make([]int, n)
6-
for i := 1; i < n; i++ {
6+
for i := 0; i < n; i++ {
77
p[i] = i
88
}
9+
size := n
910
for i := 0; i < n; i++ {
1011
for j := 0; j < n; j++ {
11-
if isConnected[i][j] == 1 {
12+
if isConnected[i][j] == 1 &&find(i) !=find(j) {
1213
p[find(i)] = find(j)
14+
size--
1315
}
1416
}
1517
}
16-
cnt := 0
17-
for i := 0; i < n; i++ {
18-
if i == find(i) {
19-
cnt++
20-
}
21-
}
22-
return cnt
18+
return size
2319
}
2420

2521
func find(x int) int {

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /