【算法学习笔记】48.递归/显式栈 SJTU OJ 1358 分割树
Description
现在有一棵树T,有N个节点,我们想通过去掉一个节点p来把T分割成更小的树,并且满足每个小树中的节点数不超过n/2。
请根据输入的树来输出所有可能的p的号码。
Input Format
第1行:一个整数N,代表有N个节点,且每个节点的编号为1,2,...,N。
第2~N行:每行两个整数x,y,代表节点x和节点y之间连通。
Output Format
从小到大一次输出满足条件的p的号码,每行1个可行解。
Input Sample
10
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10
3 8
Output Sample
3 8
想法其实很简单...
首先用邻接表存储整个图(注意, n个点 n-1个边的图除了二叉树有很多种可能.....)
然后 把每个点的每个分支的节点数计算出来 最后进行判断输出即可
//递归的描述很简单
遍历所有的点,不断的递归调用getComponent函数即可,指定源头和分支首元素。
代码如下(没用Vector):
#include <iostream> #define MaxN 10000+10 using namespace std; int n; int connect[MaxN][200]={0}; int len_c[MaxN]={0}; int seg[MaxN][200]={0}; bool caled[MaxN] = {0}; void init(){ cin>>n; //记录连通情况 O(n) for (int i = 0; i < n-1; ++i) { int x,y; cin>>x>>y; connect[x][len_c[x]++] = y; connect[y][len_c[y]++] = x; } //初始化所有只有一个分支的点的分割情况 for (int i = 1; i <= n; ++i) if(len_c[i]==1) { seg[i][0] = n-1; caled[i] = true; } //初始化有两个分支 且至少有一个分支只有一个元素的节点的分割情况 for (int i = 1; i <= n; ++i) if(len_c[i]==2) { if(len_c[connect[i][0]]==1){ seg[i][0] = 1; seg[i][1] = n-2; caled[i] = true; } if(len_c[connect[i][1]]==1){ seg[i][1] = 1; seg[i][0] = n-2; caled[i] = true; } } // } //计算与s相连的 以x开头的那一个分支有多少个节点 int getComponent(int s, int x){ int len = len_c[x]; int res = 1;//肯定有x本身 if(caled[x]){ for (int i = 0; i < len; ++i) if(connect[x][i]!=s) res += seg[x][i]; }else{//说明x的seg情况没有初始化过 int tmp = 0; for (int i = 0; i < len-1; ++i) { seg[x][i] = getComponent(x,connect[x][i]); tmp += seg[x][i]; if(connect[x][i]!=s) res += seg[x][i]; } seg[x][len-1] = n-1-tmp; caled[x] = true; } return res; } void Build(){ //去构建所有的seg for (int i = 1; i <= n; ++i) if(!caled[i]) { int len = len_c[i]; int tmp = 0; for (int j = 0; j < len-1; ++j){ //递归计算 i的以j开头的那个分支有多少个元素 seg[i][j] = getComponent(i,connect[i][j]); tmp += seg[i][j]; } seg[i][len-1] = n-1-tmp;//最后一个分支可以用补集的思想 caled[i] = true; } } void Output(){ for (int i = 1; i <= n; ++i) { bool ok = true; for (int j = 0; j < 3; ++j) if(seg[i][j]>n/2) { ok = false; break; } if(ok) cout<<i<<endl; } } int main(int argc, char const *argv[]) { init(); Build(); Output(); return 0; }
//显式栈的算法描述比较复杂 如下:
1.预处理边界点和与边界点相邻的只有两个分支的点,这些点直接处理完成。
2.找到id最小的没有处理的点,入栈。
3.当栈非空的时候:
取栈顶元素,看是否可以根据已有的情况处理它
如果可以,把它处理,抛出栈
如果不可以,把处理它需要先处理的那些节点找到,入栈。结束循环
这里要注意的一点就是不要让栈里有重复元素,否则会不断拉长。
#include <iostream> #include <cstring> #include <cstdio> #include <stack> #include <vector> #define MaxN 100010 using namespace std; int n;// 节点个数 //int connect[MaxN][10]={0};//connect[i][0,1,2] 分别存储i节点的三个分支的首元素 //int seg[MaxN][MaxN]={0};//seg[i][j] 表示i节点的第j个分支的元素个数 //int** connect; //int** seg; vector<int> connect[MaxN]; vector<int> seg[MaxN]; int len[MaxN]={0};//len[i] 表示i节点的分支的个数 bool solved[MaxN] = {false};//表示是否已经计算完i的所有分支含有节点数目 bool inStack[MaxN] = {false}; int tobe_solved[MaxN] = {0}; //还没进行处理的分支的列表 stack<int> s; void Init(){ cin>>n; //动态申请空间 //记录连通情况 O(n) for (int i = 0; i < n-1; ++i) { int x,y; scanf("%d %d",&x,&y); //connect[x][len[x]++] = y; //connect[y][len[y]++] = x; connect[x].push_back(y); connect[y].push_back(x); seg[x].push_back(0); seg[y].push_back(0); } //初始化 O(n) 以下两种情况可以直接搞定 for (int i = 1; i <= n; ++i) { if(connect[i].size()==1){ // 所有只有一个分支的点的分割情况 seg[i][0] = n-1; solved[i] = true; }else if(connect[i].size()==2){ // 有两个分支 且至少有一个分支只有一个元素的节点的分割情况 if(connect[connect[i][0]].size()==1){ seg[i][0] = 1; seg[i][1] = n-2; solved[i] = true; } if(connect[connect[i][1]].size()==1){ seg[i][1] = 1; seg[i][0] = n-2; solved[i] = true; } } } } void Output(){ //判断并输出 O(n) for (int i = 1; i <= n; ++i) { bool ok = true;//标志i点是否符合条件 for (int j = 0; j < connect[i].size(); ++j) if(seg[i][j]>n/2) {//如果存在某一个分支的节点数目>n/2 ok = false; break; } if(ok) printf("%d ",i); } return; } void Build(){ int cur = 1;//记录 //把第一个还没有处理的元素加入栈 for (; cur <= n; ++cur) if(!solved[cur]) { s.push(cur); inStack[cur] = true; break; } while(!s.empty()){ int x = s.top();//待研究元素 if(solved[x]){//如果该元素已经处理过了直接弹出 s.pop(); inStack[x] = false; }else{ //如果x已经可以处理 则处理并抛出 //否则 把需要先进行处理的元素入栈 int have_solved = 0; //已经处理过的分支的个数 int have_count = 0; //已经处理过的分支的节点总数 用于算另外一个 int tobe_solved_len = 0; //还没进行处理的分支的个数 //开始研究所有的分支 常数循环 for (int i = 0; i < connect[x].size(); ++i) { if(solved[connect[x][i]]){//如果这个分支的开头元素被处理过了 int toGet = connect[x][i]; //找到在toGet的分支中 非x的其他分支的和 + 自己 = tmp int tmp = 1; for (int j = 0; j < connect[toGet].size(); ++j) if(connect[toGet][j]!=x) tmp += seg[toGet][j]; have_count += tmp; //已经处理过的分支的节点总数累加 seg[x][i] = tmp; //x的第i个分支处理过了 have_solved++; //处理过的分支数加一 }else{ //存储没有解决的分支的id tobe_solved[tobe_solved_len++] = i; } } if(tobe_solved_len==1){ //只有一个分支还没进行处理 可以用补集 seg[x][tobe_solved[0]] = n - 1 - have_count; solved[x] = true; inStack[x] = false; s.pop(); }else if(tobe_solved_len==0){//周围的分支都处理过了 说明它也处理完成 solved[x] = true; inStack[x] = false; s.pop(); }else{//暂时不能进行处理 则把应该先处理的点加入栈 for (int k = 0; k < tobe_solved_len; ++k){ int todo = connect[x][tobe_solved[k]]; if(inStack[todo]==false){//todo如果不在栈里 才有入栈的必要 否则会把栈拉长 s.push(todo); inStack[todo] = true; } } } } if(s.empty()){ //有可能还有没处理过的点 找到id最小的加入 for (; cur <= n; ++cur) if(!solved[cur]) { s.push(cur); inStack[cur] = true; break; } } } } int main(int argc, char const *argv[]) { Init(); Build(); Output(); return 0; } /* 13 1 3 3 2 3 4 2 5 2 6 4 7 4 8 5 9 6 12 10 11 12 13 9 10 */