题目背景
XS中学化学竞赛组教练是一个酷爱炉石的人。
有一天他一边搓炉石一边监考,而你作为一个信息竞赛的大神也来凑热闹。
然而你的化竞基友却向你求助了。
“第1354题怎么做”<--手语 他问道。
题目描述
你翻到那一题:给定一个烃,只含有单键(给初中生的一个理解性解释:就是一堆碳用横线连起来,横线都是单条的)。
然后炎魔之王拉格纳罗斯用他的火焰净化了一切环(???)。所有的环状碳都变成了一个碳。如图所示。
然后指定多组碳,求出它们之间总共有多少碳。如图所示(和上图没有关系)。
但是因为在考试,所以你只能把这个答案用手语告诉你的基友。你决定用二进制来表示最后的答案。如图所示(不要在意,和题目没有什么没关系)。
输入格式
第一行两个整数n,m.表示有n个点,m根键
接下来m行每行两个整数u,v表示u号碳和v号碳有一根键
接下来一个整数tot表示询问次数
接下来tot行每行两个整数,a,b表示询问的两个碳的编号
输出格式
共tot行
每行一个二进制数
说明/提示
1<n<=10000,1<m<=50000
(两个碳不成环)
求边联通分量
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10,M=2e6+10;
int next[M],head[N],go[M],tot;
inline void add(int u,int v){
next[++tot]=head[u];head[u]=tot;go[tot]=v;
}
int dep[N];
int dfn[N],low[N],num,st[N],top;
int n,m,co[N],col,fa[N][16];
int vis[N],xx[M],yy[M],bridge[M];
inline void tarjan(int x,int f){//除了父节点判断,几乎一模一样哦
dfn[x]=low[x]=++num;
st[++top]=x;vis[x]=1;
for(int i=head[x];i;i=next[i]){
int y=go[i];
if(y==f)continue;//就这个地方不同
if(!dfn[y]){
tarjan(y,x);
low[x]=min(low[x],low[y]);
}
else if(vis[y])low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
++col;
while(st[top+1]!=x){
int y=st[top--];
co[y]=col;
}
}
}
inline void dfs2(int x,int f,int deep){
fa[x][0]=f;dep[x]=deep;
for(int i=1;i<=15;++i)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x];i;i=next[i]){
int y=go[i];
if(y==f)continue;
dfs2(y,x,deep+1);
}
}
inline int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=15;i>=0;i--)
if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
if(x==y)return x;
for(int i=15;i>=0;i--)
if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
inline void print(int x){
if(!x)return;
print(x/2);
putchar((char)((x&1)+'0'));
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;++i){
cin>>xx[i]>>yy[i];
if(xx[i]>yy[i])
swap(xx[i],yy[i]);
add(xx[i],yy[i]);
add(yy[i],xx[i]);
}
for(int i=1;i<=n;++i)
if(!dfn[i])tarjan(i,i);
tot=1;
memset(head,0,sizeof head);
memset(next,0,sizeof next);
for(int i=1;i<=m;++i)
if(co[xx[i]]!=co[yy[i]]){
add(co[xx[i]],co[yy[i]]);
add(co[yy[i]],co[xx[i]]);
}
dfs2(1,0,1);
int q,xzz,yyb;
cin>>q;
while(q--){
cin>>xzz>>yyb;
xzz=co[xzz];yyb=co[yyb];
int zsy=lca(xzz,yyb),sum;
sum=(dep[xzz]-dep[zsy]+1)+(dep[yyb]-dep[zsy]);
print(sum);
puts("");
}
}