## CSES 1705 - Forbidden Cities
[<<回主頁](https://hackmd.io/@r1cky/Sk2hKzga6)
### 題意
給你一個 $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$ 中間。
如圖 :
![image](https://hackmd.io/_uploads/B1zVDEW0T.png)
我們先固定 $a, b$。
如果 $c$ 是黃色的點或沒塗色的點(白色),那:
$c$ 和他們做 LCA 都會是跟 $c$ 同個點,也就是 $LCA(a,c)=c$ 或 $LCA(b,c)=c$,但黃色的點的話,因為他是 $LCA(a,b)$ 的祖先,所以他不是在 $a,b$ 中間。 (這個的判斷方式等等再講)
接著是綠色的點,由於 $LCA(a,c) \neq c$ 且 $LCA(b,c) \neq c$,所以他不是在 $a,b$ 中間。
而判斷祖先的方式可以用 dfs 的順序,我們隨便選一個點當根,然後做一次 dfs,對於進入和離開都加一個時間戳 $in_i, out_i$,那麼如果有一對點 $(u, v)$ 滿足 $in_u \leq in_v \leq out_v \leq out_u$,那 $u$ 就是 $v$ 的祖先。
### 將圖做處理
回到原題,他是一張圖,我們可以把它變成一棵樹嗎 ?
如果我們把環都消掉就可以了!
先想個性質,如果 $a, b$ 之間 $c$ 在一個點雙連通分量中 (vertex biconnected component),那只要 $c \neq a, b$,則 $a, b$ 一定連通,我們可以把所有點雙連通分量壓成一個點,壓法是如果一堆點屬於同一個雙連通分量,然後他們也就只屬於這個,那我們把它壓成一個點,如果不只屬於一個,也就是關節點(articulation points),那我們保留、不動這個點。
對於範測如下圖,有兩個點雙連通分量 (紅色綠色),一個關節點 (黃色) :
![image](https://hackmd.io/_uploads/SyC8oNbRp.png)
接著是處理查詢,如果 $c$ 不是關節點也不是 $a, b$,那答案就是連通。如果 $a, b$ 所在的分量中,在樹上的路徑不經過 $c$ 答案也是連通,否則就是不連通。
LCA 可以用 $O(1)$ 或 $O(logn)$ 求得,用 Tarjan 演算法求點雙連通分量是 $O(n+m)$,總時間複雜度 $O(n+m+q)$ 或 $O(n+m+qlogn)$。
### code
```cpp=
// 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";
}
}
}
}
```