http://codeforces.com/contest/902/problem/C
只要满足两个条件,即存在同构树:
①该节点上一层的节点数大于 1,
②该节点所在层节点个数大于 1。
以例 2 中的 {1,2,2} 为例:
只要将最后一个节点(即节点 5),放到上一层的倒数第二个节点(即结点 2)下,就形成了两棵同构树。
- #include<bits/stdc++.h>
- using namespace std;
- const int N = 200001;
- int main()
- {
- int height; // 树的高度 = 层数 - 1
- int cnt[N]; // 每一层的节点总数
- int parent = 0; // 根结点为1,其父节点为0
- bool flag = 1;
- cin >> height;
- for(int layer = 0; layer <= height; layer++)
- {
- cin >> cnt[layer];
- if(layer == 0)
- {
- continue;
- }
- if(cnt[layer - 1] != 1 && cnt[layer] != 1)
- {
- flag = 0;
- }
- }
- if(flag)
- {
- puts("perfect");
- return 0;
- }
- puts("ambiguous");
- for(int layer = 0; layer <= height; layer++)
- {
- // 输出该层节点的父节点
- for(int node = 1; node <= cnt[layer]; node++)
- {
- cout << parent << " ";
- }
- // 父节点指向该层的最右的那个节点
- parent += cnt[layer];
- }
- printf("\n");
- parent = 0;
- for(int layer = 0; layer <= height; layer++)
- {
- if(layer != 0 && cnt[layer - 1] != 1 && cnt[layer] != 1)
- {
- // 前n-1个节点的父节点还是原样输出
- for(int node = 1; node <= cnt[layer] - 1; node++)
- {
- cout << parent << " ";
- }
- // 最后节点的父节点往左移一个位置
- cout << parent - 1 << " ";
- parent += cnt[layer];
- continue;
- }
- for(int node = 1; node <= cnt[layer]; node++)
- {
- cout << parent << " ";
- }
- parent += cnt[layer];
- }
- return 0;
- }
来源: http://www.jianshu.com/p/6e3f8f771efe