SRM 650 div2 hard:TheKingsRoadsDiv2

完全二分木であることの必要十分条件が足りなくて何回もWAを出してしまった。

問題:http://community.topcoder.com/stat?c=problem_statement&pm=13667&rd=16314

解法:どの辺を取り除くかを全探索し、そのそれぞれについて完全二分木になる/ならないを判定する。
判定するためにはまずrootがどれになるかを調べなければならないが、これは比較的簡単で、完全二分木の性質として「rootは2つの辺を持ち、葉は1つの辺を持ち、ほかは3つの辺を持つ」という性質があるので、2つの辺を持つものをrootにすれば良い。その後、グラフが完全二分木になっているかを調べることになるが、完全二分木の条件は(木であること、すなわちループを持たないことは当然として)、
①頂点は0または2個の子を持つ
②0個の子を持つ場合、それは深さが最も深いところである
③2個の子を持つ場合、その２つの子は同じだけ子孫を持つ
これらすべてを満たすかどうかを、dfsで探索する。以下ソースコード

struct edge {
    int to;
    int id;
    edge(int t, int i) : to(t), id(i) {}
};

const int MAXN = 1050;
vector<edge> G[MAXN];

int size[MAXN];
bool visit[MAXN];

bool dfs(int v, int p, int out, int depth) {
    visit[v] = true;
    int cnt = 0;
    vector<int> tmp;
    for (auto e : G[v]) {
        if (e.id == out) continue;
        if (e.to == p) continue;
        if (visit[e.to]) return false;
        cnt++;
        if (!dfs(e.to, v, out, depth-1)) return false;
        tmp.push_back(size[e.to]);
    }
    if (cnt == 0) {
        size[v] = 1;
        return depth == 1;
    }
    if (cnt == 2) {
        if (tmp[0] != tmp[1]) return false;
        size[v] = tmp[0] + tmp[1] + 1;
        return true;
    }
    return false;
}

class TheKingsRoadsDiv2 {
public:
    string getAnswer(int h, vector <int> a, vector <int> b) {
        for (int i = 0; i < MAXN; i++) G[i].clear();
        int n = 1;
        for (int i = 0; i < h; i++) n *= 2;
        n -= 1; // nは点の数
        for (int i = 0; i < n; i++) {
            a[i]--; b[i]--;
            G[a[i]].push_back(edge(b[i], i));
            G[b[i]].push_back(edge(a[i], i));
        }
        for (int i = 0; i < n; i++) {
            // 連結の数を調べる
            int leaf = 0, root = -1, ng = 0;
            for (int j = 0; j < n; j++) {
                int cnt = 0;
                for (auto e : G[j]) {
                    if (e.id == i) continue;
                    cnt++;
                }
                if (cnt == 0) ng = 1;
                if (cnt == 1) leaf++;
                if (cnt == 2) {
                    if (root == -1) root = j;
                    else ng = 1;
                }
                if (cnt > 3) ng = 1;
            }
            printf("leaf is %d root is %d ng is %d\n", leaf, root, ng);
            if (ng == 1 || root == -1 || leaf != n/2+1) continue;
            for (int i = 0; i < n; i++) visit[i] = false;
            if (dfs(root, -1, i, h)) return "Correct";
        }
        return "Incorrect";
    }
};