CSES 1705 - Forbidden Cities

<<回主頁

題意

給你一個

$n(n\le {10}^5)$ 點

$m(m\le 2\cdot {10}^5)$ 邊、連通的無向圖，請回答

$q$ 個詢問，每次詢問給你

$(a,b,c)$，問你可不可以從

$a$ 走到

$b$ 且不經過

$c$。

想法

雖然這題是圖，但我們如果把問題改成 :

給你一個

$n$ 點

$n-1$ 邊的無根樹，請回答

$q$ 個詢問，每次詢問給你

$(a,b,c)$，問你可不可以從

$a$ 走到

$b$，其中不走到

$c$。

如果是在樹上做，那我們走的路徑會是唯一的，就會是

$LCA(a,b)$ 和

$a,b$ 之間所形成的路徑，那我們可以檢查

$c$ 有沒有在這其中，如果

$LCA(a,c)=c$ 或

$LCA(b,c)=c$ 且

$LCA(a,b)$ 是

$c$ 的祖先，那就代表

$c$ 在

$a,b$ 中間。

如圖 :

我們先固定

$a,b$。
如果

$c$ 是黃色的點或沒塗色的點(白色)，那:

$c$ 和他們做 LCA 都會是跟

$c$ 同個點，也就是

$LCA(a,c)=c$ 或

$LCA(b,c)=c$，但黃色的點的話，因為他是

$LCA(a,b)$ 的祖先，所以他不是在

$a,b$ 中間。 (這個的判斷方式等等再講)

接著是綠色的點，由於

$LCA(a,c)\ne c$ 且

$LCA(b,c)\ne c$，所以他不是在

$a,b$ 中間。

而判斷祖先的方式可以用 dfs 的順序，我們隨便選一個點當根，然後做一次 dfs，對於進入和離開都加一個時間戳

$i{n}_i,ou{t}_i$，那麼如果有一對點

$(u,v)$ 滿足

$i{n}_u\le i{n}_v\le ou{t}_v\le ou{t}_u$，那

$u$ 就是

$v$ 的祖先。

將圖做處理

回到原題，他是一張圖，我們可以把它變成一棵樹嗎 ?

如果我們把環都消掉就可以了!

先想個性質，如果

$a,b$ 之間

$c$ 在一個點雙連通分量中 (vertex biconnected component)，那只要

$c\ne a,b$，則

$a,b$ 一定連通，我們可以把所有點雙連通分量壓成一個點，壓法是如果一堆點屬於同一個雙連通分量，然後他們也就只屬於這個，那我們把它壓成一個點，如果不只屬於一個，也就是關節點(articulation points)，那我們保留、不動這個點。

對於範測如下圖，有兩個點雙連通分量 (紅色綠色)，一個關節點 (黃色) :

接著是處理查詢，如果

$c$ 不是關節點也不是

$a,b$，那答案就是連通。如果

$a,b$ 所在的分量中，在樹上的路徑不經過

$c$ 答案也是連通，否則就是不連通。

LCA 可以用

$O(1)$ 或

$O(logn)$ 求得，用 Tarjan 演算法求點雙連通分量是

$O(n+m)$，總時間複雜度

$O(n+m+q)$ 或

$O(n+m+qlogn)$。

code

// Author : rickytsung
// Problem : https://cses.fi/problemset/task/1705/
// Date : 2024/3/14
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define i64 long long
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int, int>
#define f first
#define s second
#define pb(x) push_back(x)
#define pp() pop_back()
using namespace std;

int dfs_time = 0;
const int ma = 20, maxn = 200005;
int sp[maxn][ma];
int din[maxn], dout[maxn];
 
namespace CCG{
    int cnt, n, tim;
    void tarjan_vbcc(vector<vector<int>>& bcc, vector<vector<int>>& G, int now, int pre, vector<int>& st, int* dfs, int* low){
        if(dfs[now]) return;
        dfs[now] = low[now] = ++tim;
        st.pb(now);
        for(auto& nxt:G[now]){
            if(nxt == pre) continue;
            if(!dfs[nxt]){
                 tarjan_vbcc(bcc, G, nxt, now, st, dfs, low);
                 if(low[nxt] >= dfs[now]){
                     out;
                     cnt++;
                     while(1){
                         out = st.back();
                         st.pp();
                         bcc[cnt].pb(out);
                         if(out == nxt) break;
                     }
                     bcc[cnt].pb(now);
                 }
                 low[now] = min(low[now], low[nxt]);
            }
            else{
                low[now] = min(low[now], dfs[nxt]);
            }
        }
    }
    void VBCC(vector<vector<int>>& a, vector<vector<int>>& G){
        cnt = tim = 0;
        n = G.size();
        a.resize(n+1);
        vector<int> st;
        int dfs[n] = {0}, low[n] = {0};
        for(int i = 0; i < n; i++){
            tarjan_vbcc(a, G, i, -1, st, dfs, low);
        }
        for(int i = 1; i <= n; i++){
            if(!a[i].size()){
                a.resize(i);
                break;
            }
        }
    }
}; // namespace CCG
 
void findFather(int* pa, vector<vector<int>>& T, int now, int pre){
    if(din[now])return;
    pa[now] = pre;
    din[now] = ++dfs_time;
    for(auto& nxt : T[now]){
        if(nxt == now || nxt == pre) continue;
        findFather(pa, T, nxt, now);
    }
    dout[now] = ++dfs_time;
} 
 
int LCA(int a, int b){
    if(din[a] <= din[b] && dout[a] >= dout[b]) return a;
    if(din[a] >= din[b] && dout[a] <= dout[b]) return b;
    for(int i = ma - 1; i >= 0; i--){
        if(sp[a][i] && !(din[sp[a][i]] <= din[b] && dout[sp[a][i]] >= dout[b])){
            a = sp[a][i];
        }
    }
    return sp[a][0];
}
 
int main() {
    IOS;
    int n, m, q, u, v, w;
    cin >> n >> m >> q;
    vector<vector<int>> G(n+1);
    vector<vector<int>> T(2*n+5);
    for(int i = 0; i < m; i++){
        cin >> u >> v;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    vector<vector<int>> bcc;
    CCG::VBCC(bcc, G);
    
    int in[2*n+5] = {0}, id[2*n+5] = {0}, pa[2*n+5] = {0};
    for(int i = 1; i < bcc.size(); i++){
        for(auto& j : bcc[i]){
            in[j]++;
            id[j] = i;
        }
    }
    
    int cnt = bcc.size() - 1;
    
    for(int j = 1; j <= n; j++){
        if(in[j] > 1){
            id[j] = ++cnt;
        }
    }
    
    for(int i = 1; i < bcc.size(); i++){
        for(auto& j : bcc[i]){
            T[i].pb(id[j]);
            T[id[j]].pb(i);
        }
    }
    
    for(int i = 1; i <= n; i++){
        for(auto& j:G[i]){
            if(id[i] != id[j]){
                T[id[i]].pb(id[j]);
                T[id[j]].pb(id[i]);
            }
        }
    }
    
    n = cnt;
    findFather(pa, T, id[1], 0);
    
    for(int i = 0; i <= n; i++){
        sp[i][0] = pa[i];
    }
    
    for(int j = 1; j < ma ;j++){
        for(int i = 1; i <= n; i++){
            sp[i][j] = sp[sp[i][j-1]][j-1];
        }
    }
    
    int nu, nv, nw, nuv;

    while(q--){
        cin >> u >> v >> w;
        nu = id[u];
        nv = id[v];
        nw = id[w];
        if(u == w || v == w){
            cout << "NO\n";
        }
        else if(in[w] == 1){
            cout << "YES\n";
        }
        else{
            if(LCA(nu, nw) == nw || LCA(nv, nw) == nw){
                nuv = LCA(nu, nv);
                if(din[nw] >= din[nuv] && dout[nw] <= dout[nuv]){
                    cout << "NO\n";
                }
                else{
                    cout << "YES\n";
                }
            }
            else{
              cout << "YES\n"; 
            }
        }
    }
}