topcoder 650 srm div2 1000pts

（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