ARC045 D問題 みんな仲良し高橋君

難しかったが解説を見ればまぁギリギリ理解できた。
参考にしたのは
AtCoder Regular Contest 045 解説
と
橋と関節点, lowlink - Lilliput Steps

xy座標系に点が奇数個あって、それらはxまたはyが同じ座標なら仲良くなれて、ちゃんと全員ふたり組にできるかな？という問題。
まずx座標同士が同じ点、y座標同士が同じ点を結んでグラフにするという発想がなければいけない。
そうすればそれらの連結成分のサイズが偶数個だったら必ずふたり組ずつにできるよね！というのはまぁ直感ではわかるがまぁと言った感じ。
ということで連結成分を列挙して、連結成分のサイズが奇数個のやつだけについて考える(連結成分のサイズが奇数個のやつが2つ以上存在したらひとつ点をとっても無理だしバイバイ。サイズが偶数個のやつから点とったら絶対サイズが奇数の連結成分できちゃうしバイバイ)

ある点をとった時にそれらがどのようなサイズの連結成分に分かれるかが知りたい。これはつまりグラフの関節を見つけてあげて、分かれたそれぞれのグラフがすべてサイズが偶数ならおｋということ。グラフの関節を見つけるにはlowlinkというアルゴリズムを用いる。これはslideがめっちょわかりやすい。

lowlinkは橋とか関節点とかを求めるのに重宝するらしいのでとてもお勉強になった。

typedef pair<int, int> P;

constexpr int MAX_V = 200001;

vector<int> G[MAX_V]; //lowlinkにかけるためのグラフ
vector<P> xs[MAX_V]; //xが同じもの同士
vector<P> ys[MAX_V]; //yが同じもの同士

bool used[MAX_V];
int ord[MAX_V];
int low[MAX_V];
int sum[MAX_V];
bool ans[MAX_V];
int Index = 0;

int dfs1(int v)
{
    int cnt = 1;
    used[v] = true;
    for(auto u : G[v]){
        if(!used[u]) cnt += dfs1(u);
    }
    return cnt;
}

// lowlink
int dfs2(int v, int pre)
{
    ord[v] = ++Index;
    low[v] = ord[v];
    int sum = 1;
    bool res = true;
    for(auto u : G[v]){
        if(pre == u) continue;
        if(ord[u]){
            low[v] = min(low[v], ord[u]);
        }else{
            int s =  dfs2(u, v);
            sum += s;
            low[v] = min(low[v], low[u]);
            if(pre == -1){
                if(s%2 == 1) res = false;
            }else{
                if(low[u]>=ord[v] && s%2 == 1) res = false;
            }
        }
    }
    ans[v] = res;
    return sum;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;
    rep(i, 2*N+1){
        int x, y;
        cin >> x >> y;
        x--; y--;
        xs[x].push_back(P(y, i));
        ys[y].push_back(P(x, i));
    }
    //グラフ構築(近い2点だけ取ってきてオーダーを抑える)
    for(int i=0; i<2*N+1; i++){ // x or y == iのものについて
        sort(xs[i].begin(), xs[i].end());
        sort(ys[i].begin(), ys[i].end());
        int M = (int)xs[i].size();
        for(int j=0; j<M; j++){
            for(int k=j+1; k<min(j+3, M); k++){
                G[xs[i][j].second].push_back(xs[i][k].second);
                G[xs[i][k].second].push_back(xs[i][j].second);
            }
        }
        M = (int)ys[i].size();
        for(int j=0; j<M; j++){
            for(int k=j+1; k<min(j+3, M); k++){
                G[ys[i][j].second].push_back(ys[i][k].second);
                G[ys[i][k].second].push_back(ys[i][j].second);
            }
        }
    }

    //連結成分の数を数えていく
    int link = -1;
    for(int i=0; i<2*N+1; i++){
        if(used[i]) continue;
        int cnt = dfs1(i);
        if(cnt%2 == 1){
            if(link >= 0){
                for(int j=0; j<2*N+1; j++){
                    cout << "NG" << endl;
                }
                return 0;
            }
            link = i;
        }
    }

    //lowlink
    dfs2(link, -1);
    for(int i=0; i<2*N+1; i++){
        cout << (ans[i] ? "OK" : "NG") << endl;
    }
}