Solution [COI2007] Policija
题目大意：给定一张无向图，多次询问删去一个点或一条边后，(u,v)是否连通
双连通分量，缩点
分析：
问题可以分成两个部分
Subtask1: 删去一条边之后，查询 (u,v) 是否连通
删去边 ((G_1,G_2))，只有 ((G_1,G_2)) 为割边，(u,v)才有可能不连通，这启示我们按照边双连通分量进行缩点
缩点之后的树，每一条树边都对应着一条割边，每个点都对应着一个边双连通分量，问题变成：给定一棵树，删除一条边，询问 (u,v) 是否连通
这个可以用dfs序解决，随便找个点为根，假设 $ G_1$ 的深度比 (G_2) 深，那么只要 (u,v)有一点在子树 (G_1) 内，另一点在外面就无法连通，否则可以
这个还是比较naive的
Subtask 2:删去一个点之后，查询 (u,v) 是否连通
同上，我们按照点双连通分量进行缩点
缩点之后的树，每一个点对应着原图割点，或者是去除割点之后的点双连通分量，问题变成： 给定一棵树，删除一个点 (c) ，询问 (u,v) 是否连通
仍然可以用dfs序解决，(u,v) 一个点在子树 (c) 内，另一个在外是不连通的。
除此之外还有一个特殊情况：如果 (c) 是 (u,v) 的lca，那么也是不连通的
倍增貌似会爆空间？用的树剖实现lca
代码用namespace来分割subtask，分割原图和树，虽然略显冗余但是比较清楚且不容易锅？
#include <cstdio>
#include <cctype>
#include <map>
#include <queue>
#include <stack>
using namespace std;
const int maxn = 1e5 + 100,maxm = 1e6 + 100;
inline int read(){
int x = 0;char c = getchar();
while(!isdigit(c))c = getchar();
while(isdigit(c))x = x * 10 + c - '0',c = getchar();
return x;
}
int n,m;
namespace task1{
int col_tot;
namespace graph{
vector<int> G[maxn];
inline void addedge(int u,int v){
G[u].push_back(v);}
int dep[maxn],siz[maxn],dfn[maxn],dfs_tot;
inline void dfs(int u,int faz = -1){
dep[1] = siz[u] = 1;
dfn[u] = ++dfs_tot;
for(int v : G[u]){
if(v == faz)continue;
dep[v] = dep[u] + 1;
dfs(v,u);
siz[u] += siz[v];
}
}
inline bool query(int a,int b,int x,int y){//x,y:road
if(dep[a] < dep[b])swap(a,b);
if(dep[x] < dep[y])swap(x,y);
if((dfn[a] >= dfn[x] && dfn[a] <= dfn[x] + siz[x] - 1) && (dfn[b] < dfn[x] || dfn[b] >= dfn[x] + siz[x]))return false;
if((dfn[a] < dfn[x] || dfn[a] > dfn[x] + siz[x] - 1) && (dfn[b] >= dfn[x] && dfn[b] < dfn[x] + siz[x]))return false;
return true;
}
}
struct edge{
int u,v;
}edges[maxm];
int head[maxn],nxt[maxm],tot = 1;
inline void addedge(int u,int v){
edges[++tot] = edge{u,v};
nxt[tot] = head[u];
head[u] = tot;
}
int dfn[maxn],low[maxn],iscut[maxm],dfs_tot;
inline void tarjan(int u,int faz = -1){
dfn[u] = low[u] = ++dfs_tot;
for(int i = head[u];i;i = nxt[i]){
if((i ^ 1) == faz)continue;
int v = edges[i].v;
if(!dfn[v]){
tarjan(v,i);
low[u] = min(low[u],low[v]);
if(low[v] > dfn[u])iscut[i] = iscut[i ^ 1] = 1;
}else low[u] = min(low[u],dfn[v]);
}
}
int col[maxn];
inline void bfs(int s,int c){
queue<int> q;
col[s] = c;
q.push(s);
while(!q.empty()){
int u = q.front();q.pop();
for(int i = head[u];i;i = nxt[i]){
if(iscut[i])continue;
int v = edges[i].v;
if(col[v])continue;
col[v] = c;
q.push(v);
}
}
}
inline void init(){
for(int i = 1;i <= n;i++)
if(!dfn[i])tarjan(i);
for(int i = 1;i <= n;i++)
if(!col[i])bfs(i,++col_tot);
for(int i = 2;i <= tot;i++){
int u = edges[i].u,v = edges[i].v;
if(col[u] != col[v])graph::addedge(col[u],col[v]);
}
graph::dfs(1);
}
inline bool query(int a,int b,int u,int v){
if(col[u] == col[v])return true;
return graph::query(col[a],col[b],col[u],col[v]);
}
}
namespace task2{
namespace graph{
vector<int> G[maxn << 1];
inline void addedge(int u,int v){G[u].push_back(v);}
const int maxdep = 25;
int dfn[maxn << 1],siz[maxn << 1],dep[maxn << 1],top[maxn << 1],faz[maxn << 1],son[maxn << 1],dfs_tot;
inline void dfs1(int u){
dfn[u] = ++dfs_tot;
dep[1] = siz[u] = 1;
for(int v : G[u]){
if(v == faz[u])continue;
dep[v] = dep[u] + 1;
faz[v] = u;
dfs1(v);
if(siz[v] > siz[son[u]])son[u] = v;
siz[u] += siz[v];
}
}
inline void dfs2(int u,int tp){
top[u] = tp;
if(son[u])dfs2(son[u],tp);
for(int v : G[u]){
if(v == faz[u] || v == son[u])continue;
dfs2(v,v);
}
}
inline int lca(int x,int y){
while(top[x] != top[y]){
if(dep[top[x]] > dep[top[y]])x = faz[top[x]];
else y = faz[top[y]];
}
if(dep[x] < dep[y])return x;
else return y;
}
inline int query(int a,int b,int c){
if(dep[a] < dep[b])swap(a,b);
if((dfn[a] >= dfn[c] && dfn[a] <= dfn[c] + siz[c] - 1) && (dfn[b] < dfn[c] || dfn[b] >= dfn[c] + siz[c]))return false;
if((dfn[a] < dfn[c] || dfn[a] > dfn[c] + siz[c] - 1) && (dfn[b] >= dfn[c] && dfn[b] < dfn[c] + siz[c]))return false;
if(lca(a,b) == c)return false;
return true;
}
}
vector<int> G[maxn],dcc[maxn];
inline void addedge(int u,int v){G[u].push_back(v);}
int dfn[maxn],low[maxn],iscut[maxn],col[maxn],dfs_tot,dcc_tot;
stack<int> stk;
inline void tarjan(int u){
dfn[u] = low[u] = ++dfs_tot;
stk.push(u);
int child = 0;
for(int v : G[u]){
if(!dfn[v]){
tarjan(v);
child++;
low[u] = min(low[u],low[v]);
if(low[v] >= dfn[u]){
dcc_tot++;
iscut[u] = 1;
int t;
do{
t = stk.top();stk.pop();
dcc[dcc_tot].push_back(t);
col[t] = dcc_tot;
}while(t != v);
dcc[dcc_tot].push_back(u);
}
}else low[u] = min(low[u],dfn[v]);
}
if(u == 1 && child == 1)iscut[u] = 0;
}
inline void init(){
for(int i = 1;i <= n;i++)
if(!dfn[i])tarjan(i);
int num = dcc_tot;
for(int i = 1;i <= n;i++)
if(iscut[i])col[i] = ++dcc_tot;
for(int u = 1;u <= num;u++)
for(int v : dcc[u])
if(iscut[v])graph::addedge(u,col[v]),graph::addedge(col[v],u);
graph::dfs1(1);
graph::dfs2(1,1);
}
inline bool query(int a,int b,int c){
if(!iscut[c])return true;
return graph::query(col[a],col[b],col[c]);
}
}
int main(){
n = read(),m = read();
for(int u,v,i = 1;i <= m;i++)
u = read(),v = read(),task1::addedge(u,v),task1::addedge(v,u),task2::addedge(u,v),task2::addedge(v,u);
task1::init();
task2::init();
int q = read();
while(q--){
int opt = read(),a,b,c,u,v;
if(opt == 1)a = read(),b = read(),u = read(),v = read(),puts(task1::query(a,b,u,v) ? "yes" : "no");
else a = read(),b = read(),c = read(),puts(task2::query(a,b,c) ? "yes" : "no");
}
return 0;
}