CSES - Aalto Competitive Programming 2024 - wk2 - Homework - Results
Submission details
Task:Connect cities
Sender:bielaltes
Submission time:2024-09-06 11:38:46 +0300
Language:C++ (C++11)
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.20 sdetails
#9ACCEPTED0.20 sdetails
#10ACCEPTED0.20 sdetails
#11ACCEPTED0.16 sdetails
#12ACCEPTED0.00 sdetails

Compiler report

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

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;


void dfs(int node, const vector<vector<int>>& roads, vector<bool>& visited) {
    visited[node] = true;
    for (int neighbor : roads[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, roads, visited);
        }
    }
}

int main() {
    
    int n, m;

    cin >> n >> m;

    vector< vector<int> > roads = vector<vector<int> >(n+1);
    for (int i = 0; i < m; ++i)
    {
        int aux1, aux2;

        cin >> aux1 >> aux2;

        roads[aux1].push_back(aux2);
        roads[aux2].push_back(aux1);
    }

    vector<bool> visited(n + 1, false);
    vector<int> rep;

    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            rep.push_back(i);
            dfs(i, roads, visited);
        }
    }

    int k = rep.size() - 1;
    cout << k << endl;
    for (int i = 1; i < rep.size(); ++i) {
        cout << rep[i - 1] << " " << rep[i] << endl;
    }

}

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
...
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
2 7
7 9
9 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
9 20
20 27
27 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
6 7
7 11
11 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
2 18
18 21
21 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
3 4
4 5
5 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
2 7