CSES - Aalto Competitive Programming 2024 - wk2 - Homework - Results
Submission details
Task:Connect cities
Sender:paulschulte
Submission time:2024-09-08 17:53:48 +0300
Language:C++ (C++17)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.11 sdetails
#7ACCEPTED0.11 sdetails
#8ACCEPTED0.11 sdetails
#9ACCEPTED0.11 sdetails
#10ACCEPTED0.11 sdetails
#11ACCEPTED0.15 sdetails
#12ACCEPTED0.00 sdetails

Code

// ~/.vim/cpp_template.cpp
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void dfs(int s, vector<bool> *visited, vector<int> (*adj)[]) {
if ((*visited)[s]) return;
(*visited)[s] = true;
// process node s
for (auto u: (*adj)[s]) {
dfs(u, visited, adj);
}
}
//vector<int> adj[N];
//vector<bool> visited(N, false);
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// Your code starts here
int N, M;
cin >> N >> M;
vector<int> adj[N];
vector<bool> visited(N, false);
int u, v;
for(int i = 0; i < M;i++){
cin >> u >> v;
u--;
v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
int res = 0;
vector<int> build_roads;
dfs(0, &visited, &adj);
for(int i = 0; i < N; i++){
if(visited[i]) continue;
dfs(i, &visited, &adj);
//cout << 1 << ' ' << i + 1 << endl;
build_roads.push_back(i+1);
res++;
}
cout << res << endl;
for(auto i = 0u; i < build_roads.size();i++){
cout << 1 << ' ' << build_roads[i] << 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
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