F - Well-defined Path Queries on a Namori

問題

頂点辺の連結な単純無効グラフが与えられる。グラフ上の頂点に向かう単純パスが一意に定まるか判定せよ

atcoder.jp

解法

頂点辺というのがポイント。辺の数がだった場合、任意の二つの頂点を結ぶ単純パスは一意に定まる。言い換えると、この場合は木になる。

これより、今回の辺の数では、ちょうど一つの閉路が存在することがわかる。

このままでは考えにくいので、閉路を一つの頂点とみなして考えてみる。このグラフをとする。
は木なので、上の二つの頂点を結ぶ単純パスは一意に定まる。

ただし、単純パス内に閉路を一つにまとめた頂点（縮約してできた頂点）を経由した場合は、元のグラフで一意に定まらない場合がある。
便宜上、この頂点をとする。

これに注意して考察を進めると、以下の場合分けが必要になる。
1. がを経由しないとき、一意に定まる
2. がの頂点をただ一つだけ経由するとき、一意に定まる
3. がの頂点を二つ以上経由するとき、一意に定まらない.

実装では、　上の各頂点を親として、閉路内に含まれない各頂点を探索し記録することで、経由するかしないかを判定している。あえてサイクル上の頂点から探索することで、経由しない場合でもうまく対応しているのがポイント。

以下公式の解説より

今回の問題は N 頂点, N 辺の連結グラフでしたが, 実は一般のグラフ (非連結, 非単純の場合も含む) の場合でも N 頂点 M 辺のグラフにおいて 前計算 O(N+M) 時間, 1クエリあたり O(1) 時間で判定できる必要十分条件がわかっています. 私が作成した問題ですが, 興味のあるかたはぜひ解いてみてください.

すごい。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>

using namespace std;
using Int = long long;

vector<int> cycle;
bool valid = true;

void dfs(vector<vector<int>>&edge, vector<int>&in,vector<int>&path, int v, int prev = -1)
{
    if( not valid) return;
    in[v] += 1;
    path.push_back(v);
    
    if(in[v] == 2)
    {
        cycle.push_back(v);
        
        for(auto itr = next( path.rbegin() ); itr != path.rend() && *itr != v; ++itr)
        {
            cycle.push_back(*itr);
        }
        reverse(cycle.begin(),cycle.end());
        valid = false;
        return;
    }
    for (auto nv : edge[v])
    {
        if ( nv == prev) continue;
        dfs(edge,in,path,nv, v);
    }
    
    in[v] -= 1;
    path.pop_back();
    return;
}
class unionfind {
    vector<int> par, rank, size_;
public:
    unionfind(int n) :par(n), rank(n), size_(n, 1) {
        iota(par.begin(),par.end(), 0);
    }
    int find(int x) {
        if (par[x] == x)return x;
        return par[x] = find(par[x]);
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y)return;
        if (rank[x] < rank[y])swap(x, y);
        par[y] = x;
        size_[x] += size_[y];
        if (rank[x] == rank[y])rank[x]++;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    int size(int x) {
        return size_[find(x)];
    }
};



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; cin >> N;
    vector<vector<int>>edge(N);
    
    for ( int i = 0; i < N; ++i)
    {
        int u,v; cin >> u >> v;
        --u; --v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    vector<int>in(N,0),path;
  
    dfs(edge,in,path,0);
    
    unionfind uf( N + 1 );
    map<int,int>inCycle;
    
    for(auto v : cycle)
        inCycle[v]  += 1;
    
    for(int v = 0; v < N; ++v)
    {
        for(auto nv : edge[v])
        {
            if( inCycle[nv]) continue;
            uf.unite(v,nv);
        }
    }
    
    
    
    int Q; cin >> Q;

    while (Q --> 0)
    {
        int x,y; cin >> x >> y;
        --x; --y;
        cout <<  (uf.same(x,y) ? "Yes" : "No") << endl;
        
    }
}