問題概要

二次元平面上に $2N + 1$ 個の点がある。各点について、次の問に答えよ。

その点を除去した上で、各点に対応する頂点数 $2N$ のグラフを考える。x 座標または y 座標が等しいような頂点間に辺を張る。こうしてできたグラフが完全マッチングをもつかどうかを判定せよ。

制約

$1 \le N \le 10^{5}$

考えたこと

この問題が二重頂点連結成分分解で解けるらしいこを知った上で解いたので自力ではないが、思考メモを残す。

まず、上記のようなルールで作られるグラフは、連結かつ頂点数が偶数ならば完全マッチングを持つことがわかった。数学的帰納法によって示したが、その証明は writer による補足説明と同一のものだった。逆に頂点数が奇数のものは、明らかに完全マッチングをもたない。

よって、次の問題へと帰着されることとなった。

もとの $2N+1$ 個の点についてのグラフを考える。

各点について、その点を除去したときに形成される連結成分のサイズがすべて偶数であるかどうかを判定せよ。

これは次のように解ける。

もとのグラフを単純に連結成分分解したときに、奇数サイズの連結成分が複数個あるとき：全頂点 NG
もとのグラフを単純に連結成分分解したときに、奇数サイズの連結成分が 1 個のとき：
- その奇数サイズの連結成分以外の連結成分以外の頂点はすべて NG
- その奇数サイズの連結成分を二重頂点連結成分分解して
  - 間接点以外の頂点：すべて OK
  - 間接点について
    - その間接点を除去して得られる各連結成分のサイズがすべて偶数のとき：OK
    - 奇数であるものが存在するとき：NG

ここで、間接点を除去して得られる各連結成分のサイズを求めるのは、二重頂点連結成分分解して得られる block-cut 木上で DP することで求めた。

グラフの辺数を削減する

これで解けたように思われたが、グラフを愚直に作ると、頂点数が最悪 $O(N^{2})$ 個となるので TLE してしまう。そこで、次のように考えた。

各点について、4 方向ごとに、最も近い点と 2 番目に近い点のみ辺を張ればよい

最も近い点だけでなく、2 番目に近い点にも辺を張る必要があるのは、最も近い点を削除したときに、2 番目に近い点との繋がりを残すためだ。

以上で、計算量が $O(N)$ の解法が得られた。

コード

#include <bits/stdc++.h>
using namespace std;


// Edge Class
template<class T> struct Edge {
    int from, to;
    T val;
    Edge() : from(-1), to(-1), val(-1) { }
    Edge(int f, int t, T v = -1) : from(f), to(t), val(v) {}
    friend ostream& operator << (ostream& s, const Edge& e) {
        return s << e.from << "->" << e.to;
    }
};

// graph class
template<class T> struct Graph {
    vector<vector<Edge<T>>> list;
    
    Graph() { }
    Graph(int n) : list(n) { }
    Graph(const Graph<T> &G) : list(G.list) { }
    void init(int n) {
        list.assign(n, vector<Edge<T>>());
    }
    Graph &operator = (const Graph &g) {
        list = g.list;
        return *this;
    }

    const vector<Edge<T>> &operator [] (int i) const { return list[i]; }
    const size_t size() const { return list.size(); }
    const void clear() {
        list.clear();
    }
    const void resize(int n) {
        list.resize(n);
    }

    void add_edge(int from, int to, T val = -1) {
        list[from].push_back(Edge(from, to, val));
        list[to].push_back(Edge(to, from, val));
    }

    friend ostream &operator << (ostream &s, const Graph &G) {
        s << endl;
        for (int i = 0; i < G.size(); ++i) {
            s << i << " -> ";
            for (const auto &e : G[i]) s << e.to << " ";
            s << endl;
        }
        return s;
    }
};

// low-link
template<class T> struct LowLink {
    // results
    vector<int> ord, low;
    vector<int> aps;         // articulation points
    vector<Edge<T>> brs;     // brideges

    // constructor
    LowLink() { }
    LowLink(const Graph<T> &G) {
        solve(G);
    }
    void init(const Graph<T> &G) {
        solve(G);
    }

    // solver
    int dfs(const Graph<T> &G, int t, int v, int p) {
        ord[v] = low[v] = t++;
        int num_of_children = 0;
        bool exist_articulation = false, is_multiple_edge = false;
        for (const auto &e : G[v]) {
            if (ord[e.to] == -1) {
                num_of_children++;
                t = dfs(G, t, e.to, v);
                low[v] = min(low[v], low[e.to]);  // forward edge of DFS-tree
                exist_articulation |= (p != -1) && (low[e.to] >= ord[v]);
                if (ord[v] < low[e.to]) brs.push_back(e);
            } else if (e.to != p || is_multiple_edge) {
                low[v] = min(low[v], ord[e.to]);  // back edge
            } else {
                is_multiple_edge = true;
            }
        }
        if (exist_articulation || (p == -1 && num_of_children > 1)) {
            aps.emplace_back(v);
        }
        return t;
    }

    void solve(const Graph<T> &G) {
        ord.assign(G.size(), -1), low.assign(G.size(), -1);
        for (int v = 0, k = 0; v < (int)G.size(); v++) {
            if (ord[v] == -1) k = dfs(G, k, v, -1);
        }
    }
};

// BiConnected Components decomposition
// block-cut tree (aps: 0, 1, ..., A-1, components: A, A+1, ..., A+C-1)
// (A: size of aps, C: num of components)
template<class T> struct BiConnectedComponentsDecomposition {
    // result
    LowLink<T> ll;
    vector<int> id_ap;   // index of the articulation point (size: V)
    vector<int> id_cc;   // index of the connected component (size: V)
    vector<vector<int>> groups;   // biconnected components (size: C)
    vector<vector<int>> tree;     // block-cut tree (size: A + C)

    // intermediate results
    vector<int> seen, finished;
    vector<vector<pair<int, int>>> grouped_edges;
    vector<pair<int, int>> tmp_edges;

    // constructor
    BiConnectedComponentsDecomposition() { }
    BiConnectedComponentsDecomposition(const Graph<T> &G) {
        solve(G);
    }
    void init(const Graph<T> &G) {
        solve(G);
    }

    // getter, block-cut tree to orignal graph（v: node-id of block-cut tree)
    int is_ap(int v) const {
        return (v < ll.aps.size());
    }
    int get_ap(int v) const {
        if (v >= (int)ll.aps.size()) return -1;  // not ap
        else return ll.aps[v];
    }
    int get_size(int v) const {  // including aps
        if (v < (int)ll.aps.size()) return 1;  // ap
        else return groups[v - ll.aps.size()].size();
    }
    vector<int> get_group(int v) const {
        if (v < (int)ll.aps.size()) return vector<int>({v});  // ap
        else return groups[v - ll.aps.size()];
    }

    // solver
    void dfs(const Graph<T> &G, int v, int p) {
        seen[v] = true;
        if (G[v].empty()) {
            groups.emplace_back(vector<int>({v}));
        }
        for (const auto &e : G[v]) {
            if (e.to == p) continue;
            if (!seen[e.to] || ll.ord[e.to] < ll.ord[v]) {
                tmp_edges.emplace_back(minmax(v, e.to));
            }
            if (!seen[e.to]) {
                dfs(G, e.to, v);
                if (ll.low[e.to] >= ll.ord[v]) {
                    groups.emplace_back(vector<int>({v}));
                    grouped_edges.emplace_back();
                    int ap = v;
                    while (!tmp_edges.empty()) {
                        const auto &e2 = tmp_edges.back();
                        if (!finished[e2.first] && e2.first != ap) {
                            groups.back().emplace_back(e2.first);
                            finished[e2.first] = true;
                        }
                        if (!finished[e2.second] && e2.second != ap) {
                            groups.back().emplace_back(e2.second);
                            finished[e2.second] = true;
                        }
                        grouped_edges.back().emplace_back(e2);
                        tmp_edges.pop_back();
                        if (e2.first == min(v, e.to) && e2.second == max(v, e.to)) break;
                    }
                }
            }
        }
    }

    void solve(const Graph<T> &G) {
        ll.init(G);
        seen.assign(G.size(), false), finished.assign(G.size(), false);
        for (int v = 0; v < (int)G.size(); v++) {
            if (!seen[v]) dfs(G, v, -1);
        }
        id_ap.assign(G.size(), -1), id_cc.assign(G.size(), -1);
        for (int i = 0; i < (int)ll.aps.size(); i++) {
            id_ap[ll.aps[i]] = i;
        }
        tree.assign(ll.aps.size() + grouped_edges.size(), vector<int>());
        vector<int> last(G.size(), -1);
        for (int i = 0; i < (int)grouped_edges.size(); i++) {
            vector<int> st;
            for (auto [u, v] : grouped_edges[i]) {
                st.push_back(u), st.push_back(v);
            }
            for (auto v : st) {
                if (id_ap[v] == -1) {
                    id_cc[v] = i + ll.aps.size();
                } else if (last[v] != i) {
                    tree[i + ll.aps.size()].push_back(id_ap[v]);
                    tree[id_ap[v]].push_back(i + ll.aps.size());
                    last[v] = i;
                }
            }
        }
    }
};


// Union-Find
struct UnionFind {
    // core member
    vector<int> par, nex;

    // constructor
    UnionFind() { }
    UnionFind(int N) : par(N, -1), nex(N) {
        init(N);
    }
    void init(int N) {
        par.assign(N, -1);
        nex.resize(N);
        for (int i = 0; i < N; ++i) nex[i] = i;
    }
    
    // core methods
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        swap(nex[x], nex[y]);
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
    
    // get group
    vector<int> group(int x) {
        vector<int> res({x});
        while (nex[res.back()] != x) res.push_back(nex[res.back()]);
        return res;
    }
    vector<vector<int>> groups() {
        vector<vector<int>> member(par.size());
        for (int v = 0; v < (int)par.size(); ++v) {
            member[root(v)].push_back(v);
        }
        vector<vector<int>> res;
        for (int v = 0; v < (int)par.size(); ++v) {
            if (!member[v].empty()) res.push_back(member[v]);
        }
        return res;
    }
    
    // debug
    friend ostream& operator << (ostream &s, UnionFind uf) {
        const vector<vector<int>> &gs = uf.groups();
        for (const vector<int> &g : gs) {
            s << "group: ";
            for (int v : g) s << v << " ";
            s << endl;
        }
        return s;
    }
};







#define DEBUG 1
#define COUT(x) if (DEBUG) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, deque<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, multiset<T> P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }



void ARC_045_D() {
    // 入力
    int N;
    cin >> N;
    vector<int> X(N*2+1), Y(N*2+1);
    for (int i = 0; i < N*2+1; i++) cin >> X[i] >> Y[i];

    // 横方向
    using pint = pair<int,int>;
    vector<vector<pint>> xy(N*2+2), yx(N*2+2);
    for (int i = 0; i < N*2+1; i++) {
        xy[X[i]].emplace_back(Y[i], i);
        yx[Y[i]].emplace_back(X[i], i);
    }
    for (int v = 0; v <= N*2+1; v++) {
        sort(xy[v].begin(), xy[v].end());
        sort(yx[v].begin(), yx[v].end());
    }

    // グラフを作る（横・縦に「隣接」「1個飛ばし」のみ辺を張る）
    Graph<int> G(N*2+1);
    for (int v = 0; v <= N*2+1; v++) {
        for (int i = 0; i < xy[v].size(); i++) {
            if (i+1 < xy[v].size()) G.add_edge(xy[v][i].second, xy[v][i+1].second);
            if (i+2 < xy[v].size()) G.add_edge(xy[v][i].second, xy[v][i+2].second);
        }
        for (int i = 0; i < yx[v].size(); i++) {
            if (i+1 < yx[v].size()) G.add_edge(yx[v][i].second, yx[v][i+1].second);
            if (i+2 < yx[v].size()) G.add_edge(yx[v][i].second, yx[v][i+2].second);
        }
    }

    // Block-Cut 木の構築
    BiConnectedComponentsDecomposition<int> bcc(G);

    // グラフ G の各連結成分のサイズを求めて、間接点以外の点の答えを求める
    UnionFind uf(N*2+1);
    for (int v = 0; v < N*2+1; v++) for (auto e : G[v]) uf.merge(e.from, e.to);
    int odd_num = 0;
    for (int v = 0; v < N*2+1; v++) if (uf.root(v) == v && uf.size(v) % 2 == 1) odd_num++;
    if (odd_num > 1) {
        // 奇数サイズの連結成分が複数個ある場合はすべて NG（以降、奇数サイズの連結成分は 1 個とする)
        for (int v = 0; v < N*2+1; v++) cout << "NG" << endl;
        return;
    }
    vector<bool> res(N*2+1, false);
    for (int v = 0; v < N*2+1; v++) {
        // 奇数サイズかつ間接点以外は true (間接点の結果はあとで上書きする)
        if (uf.size(v) % 2 == 1) {
            res[v] = true;
        }
    }

    // Block-Cut 木上の探索により、間接点の答えを求める
    auto tree = bcc.tree;
    vector<bool> seen(tree.size(), false);
    auto dfs = [&](auto dfs, int v, int p) -> int {
        seen[v] = true;

        // 奇数サイズの連結成分を二重頂点連結成分分解してできる Block-Cut 木を
        // 根付き木として探索したとき、各間接点について、
        // ある子頂点が存在して、それを根とする部分木のサイズが奇数ならば、"NG"
        int siz = bcc.get_size(v), odd_num = 0;
        for (auto ch : tree[v]) {
            if (ch == p) continue;
            int tmp = dfs(dfs, ch, v) - 1;
            if (tmp % 2 == 1) odd_num++;
            siz += tmp;
        }
        if (bcc.is_ap(v)) {
            int apv = bcc.get_ap(v);  // Block-cut 木の頂点 v に対応するもとのグラフの頂点
            if (uf.size(apv) % 2 == 1 && odd_num > 0) {
                res[apv] = false;
            }
        }
        return siz;
    };
    for (int v = 0; v < tree.size(); v++) {
        if (seen[v]) continue;
        dfs(dfs, v, -1);
    } 

    // 出力
    for (int v = 0; v < res.size(); v++) {
        if (res[v]) cout << "OK" << endl;
        else cout << "NG" << endl;
    }
}

int main() {
    ARC_045_D();
}