（15）
也是 DIV1 500
题意是给定 一个无向图 删去一条边以后 可不可以是完全二叉树。
细节点很多，开始做法居然求到桥去了，最近强联通写傻了。
最多1024-1个点 1024-1条边枚举
所以：
先枚举要删去的边，然后进行判断。
判断是否是一颗完全二叉树的话 要一个标记deep深度 max deep==h
然后还要看是否整个图强联通
还有一点 点的度 为1 ，2 ，3 其中度为2的只有一个 ，度为1的有2^(h-2)个
code:
#include<iostream>
#include <string>
#include <vector>
#include<cmath>
#include<map>
#include<algorithm>
#include<string.h>
using namespace std;
#define N 123456 int head[N],dfn[N],low[N];
int vis[N];
int du[N];
struct edge
{
int v,next;
}e[N*];
int cnt; int ans; void add(int u,int v)
{
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt++;
} void dfs(int u,int t)
{
vis[u]=;
t++;
ans=max(ans,t);
for (int i=head[u];i!=-;i=e[i].next)
{
int v=e[i].v;
if (!vis[v])
{
dfs(v,t);
}
}
} void init()
{
cnt=;
memset(head,-,sizeof(head));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(vis,,sizeof(vis));
memset(du,,sizeof(du));
ans=;
} class TheKingsRoadsDiv2 {
public:
string getAnswer(int h, vector <int> a, vector <int> b) {
int k=;
for (int i=;i<=h;i++) k*=;
k--; for (int p=;p<a.size();p++)
{
init();
for (int j=;j<a.size();j++)
if (j!=p)
{
add(a[j],b[j]),add(b[j],a[j]);
du[a[j]]++;
du[b[j]]++;
} int u=;
int num=;
int flag=;
for (int i=;i<=k;i++) {
if (du[i]==) u=i;
else if (du[i]==) num++;
else if (!(du[i]==||du[i]==||du[i]==)) flag=;
} if (!u||num!=(k+)/) continue;
dfs(u,);
for (int i=;i<=k;i++)
if (!vis[i]) flag=;
if (flag||ans!=h) continue;
return "Correct";
}
return "Incorrect";
}
}; // Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor