#include <bits/stdc++.h>
using namespace std;
bool ch[200009];
vector<pair<int, int> > graph[200009];
int b[200009], t[200009];
unordered_set<int> emp;
vector<int> color[200009];
vector<pair<int, int> > ans;
vector<int> comp, cols;
bool done[200009];
void dfs(int v){
ch[v] = 1;
cols.push_back(v);
for(auto [e, u]: graph[v]){
comp.push_back(e);
if(!ch[u]){
dfs(u);
}
}
}
void makemove(int occ, int e){
//printf("from=%d to=%d\n", occ, e);
ans.push_back(make_pair(occ, e));
if(t[occ]){
color[t[occ]].erase(find(color[t[occ]].begin(), color[t[occ]].end(), occ));
color[b[occ]].push_back(occ);
if(b[e]){
t[e] = t[occ];
t[occ] = 0;
}
else{
b[e] = t[occ];
t[occ] = 0;
emp.erase(e);
color[b[e]].push_back(e);
}
}
else{
color[b[occ]].erase(find(color[b[occ]].begin(), color[b[occ]].end(), occ));
emp.insert(occ);
if(b[e]){
t[e] = b[occ];
b[occ] = 0;
}
else{
b[e] = b[occ];
t[occ] = 0;
emp.erase(e);
color[b[e]].push_back(e);
}
}
}
int main(){
int n, m, i, j, ans2;
bool flag = 0;
scanf("%d %d", &n, &m);
for(i=1; i<=m; i++){
scanf("%d %d", &b[i], &t[i]);
graph[b[i]].push_back(make_pair(i, t[i]));
graph[t[i]].push_back(make_pair(i, b[i]));
if(b[i] != t[i])
flag = 1;
if(b[i] + t[i] == 0)
emp.insert(i);
}
ans2 = n;
if(n==m){
if(flag)
printf("-1\n");
else
printf("0\n");
return 0;
}
for(i=1; i<=n; i++){
if(ch[i] || graph[i][0].second == i)
continue;
comp.clear();
cols.clear();
//printf("i=%d\n", i);
dfs(i);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
queue<int> qa;
for(int v: comp){
color[t[v]].push_back(v);
//printf("t[v]=%d v=%d\n", t[v], v);
}
for(int c: cols){
if(color[c].size() >= 2)
qa.push(c);
}
if(qa.size() > m-n){
printf("-1\n");
return 0;
}
else{
ans2 += qa.size();
continue;
}
//printf("emp.size=%d\n", emp.size());
if(qa.empty()){
int occ = comp[0], e = *emp.begin();
//printf("occ=%d e=%d\n", occ, e);
makemove(occ, e);
for(int c: cols){
if(color[c].size() >= 2)
qa.push(c);
}
}
//printf("qa.size=%d\n", qa.size());
while(!qa.empty()){
//printf("qa.front=%d\n", qa.front());
if(done[qa.front()]){
qa.pop();
continue;
}
int from = color[qa.front()][0], to = color[qa.front()][1];
//printf("from=%d to=%d\n", from, to);
if(t[to])
swap(from, to);
if(t[to]){
if(emp.empty()){
printf("-1\n");
return 0;
}
int e = *emp.begin();
//printf("from=%d to=%d e=%d\n", from, to, e);
makemove(from, e);
makemove(to, e);
}
else{
makemove(from, to);
}
done[qa.front()] = 1;
qa.pop();
for(int c: {b[from], b[to]}){
if(c && color[c].size() == 2){
qa.push(c);
}
}
}
}
printf("%d\n", ans2);
return 0;
printf("%d\n", ans.size());
for(auto [u, v]: ans){
printf("%d %d\n", u, v);
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:92:16: warning: comparison of integer expressions of different signedness: 'std::queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
92 | if(qa.size() > m-n){
| ~~~~~~~~~~^~~~~
Main.cpp:145:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wformat=]
145 | printf("%d\n", ans.size());
| ~^ ~~~~~~~~~~
| | |
| int std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
| %ld
Main.cpp:54:15: warning: unused variable 'j' [-Wunused-variable]
54 | int n, m, i, j, ans2;
| ^
Main.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
58 | scanf("%d %d", &b[i], &t[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
11352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
59 ms |
22460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
11352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
11352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
11352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
11352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
