Task: | Connect cities |
Sender: | bielaltes |
Submission time: | 2024-09-06 11:38:46 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.20 s | details |
#7 | ACCEPTED | 0.20 s | details |
#8 | ACCEPTED | 0.20 s | details |
#9 | ACCEPTED | 0.20 s | details |
#10 | ACCEPTED | 0.20 s | details |
#11 | ACCEPTED | 0.16 s | details |
#12 | ACCEPTED | 0.00 s | details |
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 |