Task: | Connect cities |
Sender: | ZDHKLV |
Submission time: | 2024-09-05 17:45:37 +0300 |
Language: | Python3 (CPython3) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.02 s | details |
#2 | ACCEPTED | 0.02 s | details |
#3 | ACCEPTED | 0.02 s | details |
#4 | ACCEPTED | 0.02 s | details |
#5 | ACCEPTED | 0.02 s | details |
#6 | ACCEPTED | 0.97 s | details |
#7 | ACCEPTED | 0.95 s | details |
#8 | ACCEPTED | 0.95 s | details |
#9 | ACCEPTED | 0.95 s | details |
#10 | ACCEPTED | 0.97 s | details |
#11 | ACCEPTED | 0.24 s | details |
#12 | ACCEPTED | 0.02 s | details |
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 resultdef build_components(n: int, adj: list[list[int]]) -> list[list[int]]:"""def dfs(x: int, mark: list[int], id: int):if mark[x] != -1:returnmark[x] = idfor 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:continuemark[e] = idfor y in adj[e]:stack.append(y)id = 0mark = [-1] * nfor i in range(n):if mark[i] == -1:dfs_iterative(i, mark, id)id += 1result: list[list[int]] = [ [] for _ in range(id) ]for i in range(n):result[mark[i]].append(i)return resultdef build_paths(components: list[list[int]]) -> tuple[int, list[tuple[int, int]]]:k = len(components) - 1paths: list[tuple[int, int]] = [None] * kfor i in range(1, k+1):paths[i-1] = (components[0][0], components[i][0])return k, pathsdef 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 |