CSES - Aalto Competitive Programming 2024 - wk2 - Homework - Results
Submission details
Task:Connect cities
Sender:snude
Submission time:2024-09-06 21:16:53 +0300
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#10.01 sdetails
#20.00 sdetails
#3ACCEPTED0.00 sdetails
#40.00 sdetails
#5ACCEPTED0.00 sdetails
#60.18 sdetails
#70.18 sdetails
#80.18 sdetails
#90.18 sdetails
#100.18 sdetails
#110.01 sdetails
#120.00 sdetails

Code

#include <cstdio>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
// Depth first search
void dfs(int s, bool visited[], vector<int> adj[]) {
if (visited[s]) {
return;
};
visited[s] = true;
for (auto u: adj[s]) {
dfs(u, visited, adj);
}
}
int main (int argc, char *argv[]) {
int n, m;
cin >> n >> m;
vector<pair<int, int>> roads(m);
for (int i = 0; i < m; i++) {
cin >> roads[i].first >> roads[i].second;
}
// 0 is not included in cities
vector<int> adj[n + 1];
bool visited[n + 1];
for (int i = 0; i < n + 1; i++) visited[i] = false;
// Add roads to adjacent structure
for (int j = 0; j < m; j++) {
adj[roads[j].first].push_back(roads[j].second);
adj[roads[j].second].push_back(roads[j].first);
}
// Iterate over all the stuff
// 1. Execute initial dfs
// 2. check if there are unvisited nodes
// 3. increase the added counter and execute dfs for each unconnected component
int added = 0;
int k = 1;
while (!visited[k]) {
dfs(k, visited, adj);
for (int i = k; i < n + 1; i++) {
if (!visited[i]) {
k = i;
added++;
break;
}
}
}
/*for (int a = 0; a < n + 1; a++) {*/
/* cout << a << ": " << visited[a] << "\n";*/
/*}*/
std::cout << added << "\n";
return 0;
}

Test details

Test 1

Verdict:

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

correct output
2
1 2
2 7

user output
2

Test 2

Verdict:

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

correct output
2
1 4
4 5

user output
2

Test 3

Verdict: ACCEPTED

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

correct output
0

user output
0

Test 4

Verdict:

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

correct output
1
1 3

user output
1

Test 5

Verdict: ACCEPTED

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

correct output
0

user output
0

Test 6

Verdict:

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

Test 7

Verdict:

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

Test 8

Verdict:

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

Test 9

Verdict:

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

Test 10

Verdict:

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

Test 11

Verdict:

input
100000 1
1 2

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

user output
99998

Test 12

Verdict:

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

correct output
2
1 2
2 7

user output
2