题意
你要在两条平行直线之间画一棵有n个节点的树，树必须是可平面的（意思就是不能有两条链发生相交的情况）。给出你若干个连边（他们已经组成一棵树），问你是否可能画出符合要求的树。
思路
通过小数据找规律，可以要想把一棵树的安排在两条平行直线上，这棵树需要满足以下几个条件：
- 首先我们在树上找到一条主链
- 凡是在主链上的点，它的度数没有限制
- 与主链直接相连的点，它的度数最大为3
- 剩下的点，度数最大为2
知道了这些，接下来就是实现的问题了。这里有一种很聪明的实现方法。
- 首先，统计所有节点的度数。
- 在每一个叶子节点都发动一次DFS，在DFS过程中若遇到的一切度数小于等于2的点，进入，并做删除标记，否则返回。这一步的目的是清除掉所有叶子节点所属的链（不能直接修改度数，否则会导致删掉整棵树）。
- 重新统计每个节点的度数，因为刚才只是做标记，没有改变度数。
- 接下来对于所有曾经为3度现在为1度的点打删除标记，这种点是与主链直接相连的点。
- 重新统计每个点的度数。
- 现在每个节点的度数都理应小于3了，因为我们刚才去掉了叶子节点所在的链，如果这棵树正确，一定会删到主链上。接下来又去掉了曾经3度删完1度的节点，这相当于完全去掉了支链。这个时候整棵树理应只剩一条链了，不可能再有度数大于2的节点了。
如果理解有困难，不妨尝试画图帮助理解。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; const int MAXN = 100005; const int MAXE = 200005; int n; struct Graph { int head[MAXN]; int next[MAXE]; int end[MAXE]; int deg[MAXN]; int ndeg[MAXN]; bool del[MAXN]; int tot; void init() { tot = 2; //memset(head,0,sizeof(head)); } void addEdge(int from,int to) { end[tot] = to; next[tot] = head[from]; head[from] = tot++; deg[from]++; } } gph; void dfs(int cur,int par = 0) { if(gph.deg[cur] <= 2){ gph.del[cur] = true; for (int j = gph.head[cur]; j;j = gph.next[j]) { if(gph.end[j] != par){ dfs(gph.end[j],cur); } } } } bool judge() { for(int i = 1; i <= n; i++){ if(gph.deg[i] == 1){ dfs(i); } } for(int i = 1; i <= n; i++) { if(gph.deg[i] >= 3) { int ndeg = 0; for(int j = gph.head[i]; j; j = gph.next[j]) { if(!gph.del[gph.end[j]]) { ndeg++; } } gph.ndeg[i] = ndeg; } } for(int i = 1; i<= n; i++) { if(gph.deg[i] == 3 && gph.ndeg[i] == 1) { gph.del[i] = true; } } for(int i = 1; i <= n; i++) { if(!gph.del[i]) { int fdeg = 0; for(int j = gph.head[i]; j; j = gph.next[j]) { if(!gph.del[gph.end[j]]) { fdeg++; } } if(fdeg > 2) { return false; } } } return true; } int main() { gph.init(); scanf(" %d",&n); for(int i = 1; i < n; i++) { int a,b; scanf(" %d %d",&a,&b); gph.addEdge(a,b); gph.addEdge(b,a); } if(judge()) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; } |
