rockdu
Monocarp has drawn a tree (an undirected connected acyclic graph) and then has given each vertex an index. All indices are distinct numbers from 11 to nn. For every edge ee of this tree, Monocarp has written two numbers: the maximum indices of the vertices of the two components formed if the edge ee (and only this edge) is erased from the tree.
Monocarp has given you a list of n−1n−1 pairs of numbers. He wants you to provide an example of a tree that will produce the said list if this tree exists. If such tree does not exist, say so.
The first line contains one integer nn (2≤n≤10002≤n≤1000) — the number of vertices in the tree.
Each of the next n−1n−1 lines contains two integers aiai and bibi each (1≤ai<bi≤n1≤ai<bi≤n) — the maximal indices of vertices in the components formed if the ii-th edge is removed.
If there is no such tree that can produce the given list of pairs, print "NO" (without quotes).
Otherwise print "YES" (without quotes) in the first line and the edges of the tree in the next n−1n−1 lines. Each of the last n−1n−1 lines should contain two integers xixi and yiyi (1≤xi,yi≤n1≤xi,yi≤n) — vertices connected by an edge.
Note: The numeration of edges doesn't matter for this task. Your solution will be considered correct if your tree produces the same pairs as given in the input file (possibly reordered). That means that you can print the edges of the tree you reconstructed in any order.
4
3 4
1 4
3 4
YES
1 3
3 2
2 4
3
1 3
1 3
NO
3
1 2
2 3
NO
Possible tree from the first example. Dotted lines show edges you need to remove to get appropriate pairs.
CF有史以来A的第一个构造题(虽然水的一逼)
首先，N节点一定会出现在每一个边中，否则不合法。
考虑怎么构造，我们可以直接做一个菊花图，N在中间，在条件里涉及的点全是叶子。每一个叶子在原来出现了k次，到根的路径就要长度为k，我们从小的开始贪心满足就行了。
#include<cstdio>
#include<vector>
using namespace std;
const int maxn = 1e3 + 5;
int n, vis[maxn], u, v, tot[maxn], lft, usd;
int need, cnt;
vector<int > hd[maxn];
int main() {
scanf("%d", &n);
for(register int i = 1; i < n; ++i) {
scanf("%d%d", &u, &v);
if(u == v) return printf("NO"), 0;
if(u != n && v != n) return printf("NO"), 0;
if(u == n) {
++tot[v], vis[v] = 1;
}
else {
++tot[u], vis[u] = 1;
}
}
for(register int i = 1; i <= n; ++i) {
cnt = 0;
if(tot[i])
for(register int j = 1; j < i; ++j) {
if(cnt == tot[i] - 1) break;
if(!vis[j]) hd[i].push_back(j), vis[j] = 1, ++cnt;
}
if(cnt < tot[i] - 1)
return printf("NO"), 0;
}
printf("YES\n");
for(register int i = 1; i < n; ++i) {
if(tot[i]) {
int last = n;
for(register int j = hd[i].size() - 1; j >= 0; --j) {
printf("%d %d\n", last, hd[i][j]), last = hd[i][j];
}
printf("%d %d\n", last, i);
}
}
return 0;
}
没有帐号? 立即注册