网站做业务赚钱,特网站建设,如何介绍自己的网页设计,做网站的客户哪里找每次找到所有叶子节点#xff0c;把它们的父亲染白#xff0c;自己染黑。这个时候染完的叶子节点及其父亲节点对树的其他部分已无影响 ,可以直接删掉。
那么只需要判断树的其他部分是否有先手必胜策略即可。用递归遍历。
边界条件#xff1a;若树为单一节点先手必胜。
代…每次找到所有叶子节点把它们的父亲染白自己染黑。这个时候染完的叶子节点及其父亲节点对树的其他部分已无影响 ,可以直接删掉。
那么只需要判断树的其他部分是否有先手必胜策略即可。用递归遍历。
边界条件若树为单一节点先手必胜。
代码
#includeiostream
#includecstdio
using namespace std;
const int N1e55;
struct Edge{int v,nxt;
}e[N1];
int n,flag[N],cnt,head[N];
void add(int x,int y){e[cnt].vy;e[cnt].nxthead[x];head[x]cnt;
}
bool dfs(int x,int fa){flag[x]1;int tot0;for(int ihead[x];i;ie[i].nxt){int ve[i].v;if(vfa) continue;if(dfs(v,x)) return true;if(flag[v]){tot;flag[x]0;if(tot2)return true;}}return false;
}
int main(){scanf(%d,n);int x,y;for(int i1;in;i){scanf(%d%d,x,y);add(x,y);add(y,x);}printf(dfs(1,0)||flag[1]?First:Second);return 0;
}
