题目描述
“我有个愿望，我希望在灿烂千阳时遇见你。”
这是个有n个点的世界，有m条无向边连接着这n个点，但是不保证点之间能够互相到达。
“这个世界的夕阳，只在奇数长的简单路径的尽头。”一个神如是说。
于是我想知道对于一个点对(x,y)，x到y之间的所有简单路径中是否存在长度为奇数的路径，只有这样，我才能找到存在有夕阳的路。
输入
第一行两个数n和m表示点的个数和边的条数。
接下来m行，每行两个数x,y表示x和y之间存在一条无向边。
接下来一行一个整数q表示询问的个数。
下面q行每行两个整数x,y表示一组询问，问x到y的所有简单路径中是否存在有长度为奇数的路径
输出
对于每组询问x,y，如果x与y之间存在一条长度为奇数的简单路径那么输出Yes否则输出No
样例输入
样例输出
No
Yes
Yes
Yes
No
Yes
Yes
Yes
数据范围
对于50%的数据，1≤n,m,q≤500
对于100%的数据,,1≤n,q,m≤100000
保证没有自环与重边。
题解：
若对原图解出生成树森林，那么询问点对(x,y)见是否有简单路径长度为奇数，可以看作求点对(x,y)是否有边在奇环上。
于是问题转化为判断是否有边在奇环中，这里解图的强联通分量，对于一个强联通分量，若其中有边在奇环上，那么分量中的所有边都在某个奇环上。
为了在分量中找到在奇环上的边，对图作tarjan算法，若点对(x,y)的深度的奇偶性相同，那么x和y的路径上的边都在奇环中。
#include<math.h>
#include<stdio.h>
#include<string.h>
#define buf 100001
#define MAXBUF 1<<9
#define dmin(a,b) ((a)<(b)?(a):(b))
inline void swp(int &x,int &y){
x^=y,
y^=x,
x^=y;
}
char B[MAXBUF],*S=B,*T=B;
inline char gt(){
if(S==T){
T=(S=B)+fread(B,,MAXBUF,stdin);
if(S==T)
return ;
}
return *S++;
}
inline void F(int &x){
x=;int c=gt(),f=;
for(;c<||c>;c=gt())
if(!(c^))
f=-;
for(;c>&&c<;c=gt())
x=(x<<)+(x<<)+c-;
x*=f;
}
struct Pointer{
int to;
Pointer *nxt;
}*fst[buf];
Pointer mem[buf<<],*tot=mem;
inline void link(int a,int b){
*++tot=(Pointer){b,fst[a]},fst[a]=tot;
*++tot=(Pointer){a,fst[b]},fst[b]=tot;
}
bool odd[buf];
int bin[],n,m,dfn[buf],dep[buf],fa[buf][],tim,s[buf],top,pb[buf],timer,low[buf],scn[buf],scx;
void tarjan(int x){
pb[++top]=x;
dfn[x]=low[x]=++timer;
for(int i=;i<=tim;i++)
fa[x][i]=fa[fa[x][i-]][i-];
for(Pointer *iter=fst[x];iter;iter=iter->nxt)
if(iter->to^fa[x][])
if(!dfn[iter->to])
fa[iter->to][]=x,
dep[iter->to]=dep[x]+,
tarjan(iter->to),
low[x]=dmin(low[x],low[iter->to]);
else
if(!scn[iter->to]){
low[x]=dmin(low[x],dfn[iter->to]);
if(!((dep[iter->to]&)^(dep[x]&)))
odd[x]=;
}
if(!(dfn[x]^low[x])){
bool f=;
int v=top;
for(;pb[v]^x;)
f|=odd[pb[v--]];
if(f)
for(v++;v<=top;v++)
s[pb[v]]++;
++scx;
do
v=pb[top--],
scn[v]=scx;
while(v^x);
}
}
void dfs(int x){
for(Pointer *iter=fst[x];iter;iter=iter->nxt)
if(!(fa[iter->to][]^x))
s[iter->to]+=s[x],
dfs(iter->to);
}
int lca(int x,int y){
if(dep[x]<dep[y])
swp(x,y);
for(int i=tim;i>=;i--)
if(dep[fa[x][i]]>=dep[y])
x=fa[x][i];
if(!(x^y))
return x;
for(int i=tim;i>=;i--)
if(fa[x][i]^fa[y][i])
x=fa[x][i],
y=fa[y][i];
return fa[x][];
}
int main(){
freopen("sunset.in","r",stdin),
freopen("sunset.out","w",stdout);
F(n),F(m);
tim=log(n)/log()+;
bin[]=;
for(int i=;i<=tim;i++)
bin[i]=bin[i-]<<;
for(int x,y;m;m--)
F(x),
F(y),
link(x,y);
for(int i=;i<=n;i++)
if(!dfn[i])
dep[i]=,
fa[i][]=i,
tarjan(i);
for(int i=;i<=n;i++)
if(!(fa[i][]^i))
dfs(i);
int q,x,y,t;
for(F(q);q;q--){
F(x),F(y);
if(fa[x][tim]^fa[y][tim])
puts("No");
else
t=lca(x,y),
puts(((dep[x]+dep[y]-(dep[t]<<))&
||s[x]+s[y]-(s[t]<<)>)?
"Yes":
"No");
}
fclose(stdin),
fclose(stdout);
}