Submission details
Task:Connect cities
Sender:aalto26bh_045
Submission time:2026-09-04 11:46:43 +0300
Language:C++ (C++20)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.20 sdetails
#7ACCEPTED0.20 sdetails
#8ACCEPTED0.21 sdetails
#9ACCEPTED0.21 sdetails
#10ACCEPTED0.20 sdetails
#11ACCEPTED0.17 sdetails
#12ACCEPTED0.00 sdetails

Compiler report

input/code.cpp: In function 'int main(int, char**)':
input/code.cpp:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i + 1 < starts.size(); i++) {
      |                     ~~~~~~^~~~~~~~~~~~~~~

Code

#include <iostream>
#include <map>
#include <unistd.h>
#include <vector>


int main(int argc, char** argv) {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> neightbours(n + 1);

    for (int x=0; x<m; x++) {
        int a, b;
        std::cin >> a >> b;
        neightbours[a].push_back(b);
        neightbours[b].push_back(a);
    }

    std::vector<bool> visited(n + 1, false);

    std::vector<int> starts;
    
    for (int i=1; i<=n; i++) {
        if (visited[i]) continue;

        starts.push_back(i);
        visited[i] = true;
        std::vector<int> to_visit = {i};

        while (!to_visit.empty()) {
            int city = to_visit.back();
            to_visit.pop_back();

            for (int neightbour : neightbours[city]) {
                if (!visited[neightbour]) {
                    visited[neightbour] = true;
                    to_visit.push_back(neightbour);
                }
            }
        }
    }
    
    std::cout << starts.size() -1 << std::endl;
    for (int i = 0; i + 1 < starts.size(); i++) {
        std::cout << starts[i] << " " << starts[i+1] << std::endl;
    }
    

    return 0;
}

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
2 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
4 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
2 3
3 4
4 5
...

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
2 7
7 9
9 15
...

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
9 20
20 27
27 28
...

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
6 7
7 11
11 12
...

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
2 18
18 21
21 27
...

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
3 4
4 5
5 6
...

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
2 7