Task: | Connect cities |
Sender: | minghao |
Submission time: | 2024-09-08 23:24:44 +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.07 s | details |
#7 | ACCEPTED | 0.06 s | details |
#8 | ACCEPTED | 0.06 s | details |
#9 | ACCEPTED | 0.06 s | details |
#10 | ACCEPTED | 0.07 s | details |
#11 | ACCEPTED | 0.05 s | details |
#12 | ACCEPTED | 0.00 s | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:55:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wformat=] 55 | printf("%d\n", ans.size()-1); | ~^ ~~~~~~~~~~~~ | | | | int std::set<int>::size_type {aka long unsigned int} | %ld input/code.cpp: In function 'void Test()': input/code.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result] 33 | freopen("temp\\in.txt", "r", stdin); | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~ input/code.cpp: In function 'int main()': input/code.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result] 39 | scanf("%d%d", &n, &m); | ~~~~~^~~~~~~~~~~~...
Code
#include<iostream> #include<cstdio> #include<algorithm> #include<set> typedef long long LL; const int N=100005; // Union&Find Start int father[N], size[N]; int Find(int x) { if(father[x]==x) return x; return father[x]=Find(father[x]); } void Union(int x, int y) { x = Find(x), y=Find(y); if(x==y) return; if(size[x] < size[y]) std::swap(x, y); father[y] = x; size[x] += size[y]; } // Union&Find End void Test() { freopen("temp\\in.txt", "r", stdin); } int main() { // Test(); int n, m; scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) father[i]=i; for(int i=1; i<=m; i++) { int a, b; scanf("%d%d", &a, &b); Union(a, b); } std::set<int> ans; for(int i=1; i<=n; i++) ans.insert(Find(i)); // P printf("%d\n", ans.size()-1); int last = *ans.begin(); for(auto it=ans.begin(); it!=ans.end(); it++) { if(it==ans.begin()) continue; int now = *it; printf("%d %d\n", last, now); last = now; } 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 3 3 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 2 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 3 6 |
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 3 3 11 11 14 14 17 ... 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 7 7 9 9 15 15 16 ... 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 9 20 20 27 27 28 28 33 ... 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 6 7 7 11 11 12 12 30 ... 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 18 21 21 27 27 28 28 29 ... 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 3 3 7 |