CSES - Aalto Competitive Programming 2024 - wk2 - Homework - Results
Submission details
Task:Connect cities
Sender:ZDHKLV
Submission time:2024-09-05 17:45:37 +0300
Language:Python3 (CPython3)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.02 sdetails
#2ACCEPTED0.02 sdetails
#3ACCEPTED0.02 sdetails
#4ACCEPTED0.02 sdetails
#5ACCEPTED0.02 sdetails
#6ACCEPTED0.97 sdetails
#7ACCEPTED0.95 sdetails
#8ACCEPTED0.95 sdetails
#9ACCEPTED0.95 sdetails
#10ACCEPTED0.97 sdetails
#11ACCEPTED0.24 sdetails
#12ACCEPTED0.02 sdetails

Code

N, M = [ int(x) for x in input("").split(" ") ]
ROADS = [ [ int(x)-1 for x in input("").split(" ") ] for _ in range(M) ]
def build_adjacency(n: int, roads: list[tuple[int, int]]) -> list[list[int]]:
result: list[list[int]] = [ [] for _ in range(n) ]
for a, b in roads:
result[a].append(b)
result[b].append(a)
return result
def build_components(n: int, adj: list[list[int]]) -> list[list[int]]:
"""
def dfs(x: int, mark: list[int], id: int):
if mark[x] != -1:
return
mark[x] = id
for y in adj[x]:
dfs(y, mark, id)
"""
def dfs_iterative(x: int, mark: list[int], id: int):
stack = [x]
while len(stack) > 0:
e = stack.pop()
if mark[e] != -1:
continue
mark[e] = id
for y in adj[e]:
stack.append(y)
id = 0
mark = [-1] * n
for i in range(n):
if mark[i] == -1:
dfs_iterative(i, mark, id)
id += 1
result: list[list[int]] = [ [] for _ in range(id) ]
for i in range(n):
result[mark[i]].append(i)
return result
def build_paths(components: list[list[int]]) -> tuple[int, list[tuple[int, int]]]:
k = len(components) - 1
paths: list[tuple[int, int]] = [None] * k
for i in range(1, k+1):
paths[i-1] = (components[0][0], components[i][0])
return k, paths
def solve(n: int, roads: list[tuple[int, int]]):
k, paths = build_paths(build_components(n, build_adjacency(n, roads)))
print(k)
for a, b in paths:
print(f"{a+1} {b+1}")
solve(N, ROADS)

Test details

Test 1

Verdict: ACCEPTED

input
10 10
2 5
5 6
1 4
6 8
...

correct output
2
1 2
2 7

user output
2
1 2
1 7

Test 2

Verdict: ACCEPTED

input
10 10
3 9
6 8
9 10
7 8
...

correct output
2
1 4
4 5

user output
2
1 4
1 5

Test 3

Verdict: ACCEPTED

input
10 10
7 9
1 7
1 3
3 4
...

correct output
0

user output
0

Test 4

Verdict: ACCEPTED

input
10 10
4 8
5 9
4 9
2 7
...

correct output
1
1 3

user output
1
1 3

Test 5

Verdict: ACCEPTED

input
10 10
4 9
2 4
7 10
1 8
...

correct output
0

user output
0

Test 6

Verdict: ACCEPTED

input
100000 200000
7233 22146
94937 96203
6133 10731
98737 99193
...

correct output
4785
1 2
2 3
3 4
4 5
...

user output
4785
1 2
1 3
1 4
1 5
...
Truncated

Test 7

Verdict: ACCEPTED

input
100000 200000
92950 93575
24401 88897
41796 99364
47106 50330
...

correct output
4868
1 2
2 7
7 9
9 15
...

user output
4868
1 2
1 7
1 9
1 15
...
Truncated

Test 8

Verdict: ACCEPTED

input
100000 200000
15637 76736
79169 98809
4382 86557
73383 77029
...

correct output
4683
1 9
9 20
20 27
27 28
...

user output
4683
1 9
1 20
1 27
1 28
...
Truncated

Test 9

Verdict: ACCEPTED

input
100000 200000
47932 66981
86401 99942
4353 27841
60492 67345
...

correct output
4807
1 6
6 7
7 11
11 12
...

user output
4807
1 6
1 7
1 11
1 12
...
Truncated

Test 10

Verdict: ACCEPTED

input
100000 200000
6554 44548
76413 98555
5447 59589
70166 74434
...

correct output
4786
1 2
2 18
18 21
21 27
...

user output
4786
1 2
1 18
1 21
1 27
...
Truncated

Test 11

Verdict: ACCEPTED

input
100000 1
1 2

correct output
99998
1 3
3 4
4 5
5 6
...

user output
99998
1 3
1 4
1 5
1 6
...
Truncated

Test 12

Verdict: ACCEPTED

input
10 9
2 5
5 6
1 4
6 8
...

correct output
2
1 2
2 7

user output
2
1 2
1 7