C - Graph Palindrome

2 secs 1024 MB

matcharate12

Problem

Submissions

Test cases

Editorial

この問題は主にグラフ探索を問います。

与えられたグラフに対して深さ優先探索などのグラフ探索アルゴリズムを用い、条件を満たす $(i,j)$ を全探索して $O(N^2(N+M))$ で判定したいところですが、制約からこの方法では間に合いません。

グラフ探索アルゴリズムは、通常ある $1$ つの頂点に対し隣接する辺をたどりながら行くことのできる頂点を全探索します。
なので毎回 $i$ に対して $j=1,2,\dots N$ (ただし $i\ne j$ ) で探索しなくてよいことがわかります(無駄に多くの計算をしてしまっているため)。これより探索パートは $O(N(N+M))$ で実装することが可能です。

次に本問題の条件判定について考えます。次のような配列 $C$ を定義します。

$C[i][j]:=$ $2$ 頂点 $i,j$ を互いに辺をたどりながらたどり着けることができるか？( $\text{True or False}$ )

探索パートにより $i=1,2,\dots,N$ に対して頂点 $i$ から辺をたどって行くことのできる頂点は探索済です。よってこの情報を利用して更新することができます。
最終的な判定は、すべての $i,j$ に対し、

$C[i][j]=\text{True}$ かつ $C[N-i+1][N-j+1]=\text{True}$
$C[i][j]=\text{False}$ かつ $C[N-i+1][N-j+1]=\text{False}$

(ゆえにこの判定は $C[i][j]=C[N-i+1][N-j+1]$ が成り立つかどうか判定することと同値であることが分かります)

が成り立てば Yes、 $1$ つでも成り立たないものがあれば No となります。
以上から $O(N(N+M))$ で実装することができました。

※ $N^2$ が含まれていますが、これは探索が終わった後に頂点 $i$ からたどりつける $j$ を確認するため、 $1$ つの $i$ に対して $N$ 回の計算が必要です。

別解として、伝家の宝刀であるUnionFindという素集合データ構造を用いて実装することによって $O(N^2\alpha(N))$ ※で実装することもできます。

※ $\alpha(N)$ はアッカーマンの逆関数を表します。

xxxxxxxxxx
 
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)
#define srep(i,a,b) for(int i = a; i < b; i++) //[a,b)
using namespace std;
using ll = long long;
​
struct UnionFind {
    vector<int> par,rank,siz;
    UnionFind(int n):par(n,-1),rank(n,0),siz(n,1) {}
​
    int root(int x){
        if(par[x] == -1) return x;
        return par[x] = root(par[x]);
    }
​
    bool same(int x,int y){
        int rx = root(x),ry = root(y);
        return rx == ry;
    }
​
    bool unite(int x,int y){
        int rx = root(x),ry = root(y);
        if(rx == ry) return 0;
​
        //union by rank
        if(rank[rx] < rank[ry]) swap(rx,ry);
        par[ry] = rx;
        if(rank[ry] == rank[rx]) rank[rx]++;
        siz[rx] += siz[ry];
        return 1;
    }
​
    int size(int x){ return siz[root(x)]; }
};
​
int main(){
    int N,M; cin >> N >> M;
    UnionFind uf(N);
​
    rep(_,M){
        int A,B; cin >> A >> B;
        A--; B--;
        uf.unite(A,B);
    }
​
    bool ok = 1;
    rep(i,N){
        srep(j,i+1,N){
            bool aok = uf.same(N-i-1,N-j-1);
            bool aok2 = uf.same(i,j);
            if(aok != aok2) ok = 0;
        }
    }
    cout << (ok ? "Yes" : "No");
}
​