#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
int n, d[N];
vector<int> g[N], leaf;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // use mt19937_64 for 64 bit
int Rand(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
int tym, st[N], low[N], vis[N];
int dfs(int u, int f) {
vis[u] = 1;
low[u] = st[u] = tym++;
for(int v : g[u]) {
if(v == f) continue;
if(vis[v]) low[u] = min(low[u], st[v]);
else {
int good = dfs(v,u);
if(!good) return 0;
low[u] = min(low[u], low[v]);
}
if(d[u] < low[v]) return 0;
} return 1;
}
bool ok() {
memset(vis,0,sizeof vis);
tym = 0;
return dfs(1,-1);
}
int main() {
scanf("%d", &n);
for(int i = 1; i < n; i++) {
int u, v; scanf("%d %d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
d[u]++, d[v]++;
}
for(int i = 1; i <= n; i++) if(d[i] == 1)
leaf.push_back(i);
int sz = leaf.size();
printf("%d\n", (int)ceil(sz/2.));
for(;;) {
for(int i = 0; i < sz; i++)
swap(leaf[i], leaf[Rand(0,sz-1)]);
for(int i = 0; i < sz; i+=2) {
if(i+1 < sz) {
g[leaf[i]].push_back(leaf[i+1]);
g[leaf[i+1]].push_back(leaf[i]);
} else {
g[leaf[i]].push_back(leaf[0]);
g[leaf[0]].push_back(leaf[i]);
}
}
if(ok()) {
for(int i = 0; i < sz; i+=2) {
if(i+1 < sz) printf("%d %d\n", leaf[i], leaf[i+1]);
else printf("%d %d\n", leaf[i], leaf[0]);
} return 0;
}
for(int i = 0; i < sz; i+=2) {
if(i+1 < sz) {
g[leaf[i]].pop_back();
g[leaf[i+1]].pop_back();
} else {
g[leaf[i]].pop_back();
g[leaf[0]].pop_back();
}
}
}
return 0;
}
Compilation message
net.cpp: In function 'int main()':
net.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
net.cpp:36:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u, v; scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
14072 KB |
Output is correct |
2 |
Correct |
13 ms |
14204 KB |
Output is correct |
3 |
Correct |
13 ms |
14404 KB |
Output is correct |
4 |
Correct |
13 ms |
14404 KB |
Output is correct |
5 |
Correct |
13 ms |
14404 KB |
Output is correct |
6 |
Correct |
13 ms |
14404 KB |
Output is correct |
7 |
Correct |
15 ms |
14404 KB |
Output is correct |
8 |
Correct |
17 ms |
14404 KB |
Output is correct |
9 |
Correct |
13 ms |
14404 KB |
Output is correct |
10 |
Correct |
13 ms |
14404 KB |
Output is correct |
11 |
Execution timed out |
2068 ms |
14404 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
14072 KB |
Output is correct |
2 |
Correct |
13 ms |
14204 KB |
Output is correct |
3 |
Correct |
13 ms |
14404 KB |
Output is correct |
4 |
Correct |
13 ms |
14404 KB |
Output is correct |
5 |
Correct |
13 ms |
14404 KB |
Output is correct |
6 |
Correct |
13 ms |
14404 KB |
Output is correct |
7 |
Correct |
15 ms |
14404 KB |
Output is correct |
8 |
Correct |
17 ms |
14404 KB |
Output is correct |
9 |
Correct |
13 ms |
14404 KB |
Output is correct |
10 |
Correct |
13 ms |
14404 KB |
Output is correct |
11 |
Execution timed out |
2068 ms |
14404 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
14072 KB |
Output is correct |
2 |
Correct |
13 ms |
14204 KB |
Output is correct |
3 |
Correct |
13 ms |
14404 KB |
Output is correct |
4 |
Correct |
13 ms |
14404 KB |
Output is correct |
5 |
Correct |
13 ms |
14404 KB |
Output is correct |
6 |
Correct |
13 ms |
14404 KB |
Output is correct |
7 |
Correct |
15 ms |
14404 KB |
Output is correct |
8 |
Correct |
17 ms |
14404 KB |
Output is correct |
9 |
Correct |
13 ms |
14404 KB |
Output is correct |
10 |
Correct |
13 ms |
14404 KB |
Output is correct |
11 |
Execution timed out |
2068 ms |
14404 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |