题目背景
XS中学化学竞赛组教练是一个酷爱炉石的人。
有一天他一边搓炉石一边监考，而你作为一个信息竞赛的大神也来凑热闹。
然而你的化竞基友却向你求助了。
“第1354题怎么做”<--手语 他问道。
题目描述
你翻到那一题：给定一个烃，只含有单键（给初中生的一个理解性解释：就是一堆碳用横线连起来，横线都是单条的）。
然后炎魔之王拉格纳罗斯用他的火焰净化了一切环（？？？）。所有的环状碳都变成了一个碳。如图所示。
然后指定多组碳，求出它们之间总共有多少碳。如图所示（和上图没有关系）。
但是因为在考试，所以你只能把这个答案用手语告诉你的基友。你决定用二进制来表示最后的答案。如图所示（不要在意，和题目没有什么没关系）。
输入输出格式
输入格式：
第一行两个整数n,m.表示有n个点，m根键
接下来m行每行两个整数u，v表示u号碳和v号碳有一根键
接下来一个整数tot表示询问次数
接下来tot行每行两个整数，a,b表示询问的两个碳的编号
输出格式：
共tot行
每行一个二进制数
输入输出样例
输入样例：
3 2
1 2
2 3
2
1 2
2 3
输出样例：
10
10双连通分量+lca求距离不知道为什么是黑题，连我这种小蒟蒻都会的。。主要是tarjan和lca求距离以及缩点重建图直接上代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
using namespace std;
inline int read(){
int x=
0;
bool f=
1;
char c=
getchar();
while(!isdigit(c)){
if(c==
'-')f=
0;c=
getchar();}
while(isdigit(c)){x=x*
10+c-
'0';c=
getchar();}
if(!f)
return 0-
x;
return x;
}
const int M=
10010;
const int N=
50010;
vector<
int>e[M];
//无权图,直接存vector
vector<
int>
g[M];
int n,m,tot,dfn[M],low[M],vis[M],color[M],tim,megumi,x[N],y[N],f[M][
25],depth[M],QAQ;
stack<
int>
s;
inline void tarjan(
int u,
int fa){
dfn[u]=low[u]=++
tim;
s.push(u);
for(
int i=
0;i<e[u].size();i++
){
int v=
e[u][i];
if(v==fa)
continue;
//双连通分量
if(!
dfn[v]){
tarjan(v,u);
low[u]=
min(low[u],low[v]);
}
else if(!color[v]) low[u]=
min(low[u],dfn[v]);
}
if(low[u]==
dfn[u]){
++
megumi;
while(s.top()!=
u){
color[s.top()]=
megumi;
s.pop();
}
color[s.top()]=
megumi;
s.pop();
}
}
inline void rebuild(){
for(
int i=
1;i<=m;i++
){
if(color[x[i]]^
color[y[i]])
g[color[x[i]]].push_back(color[y[i]]),g[color[y[i]]].push_back(color[x[i]]);//必须是color[x[i]],卡了半个小时qwq
}
}
inline void dfs(
int u,
int fa){
if(vis[u])
return ;
vis[u]=
1;
depth[u]=depth[fa]+
1;
for(
int i=
1;i<=
20;i++
){
f[u][i]=f[f[u][i-
1]][i-
1];
}
for(
int i=
0;i<g[u].size();i++
){
int v=
g[u][i];
if(v==fa)
continue;
f[v][0]=
u;
dfs(v,u);
}
}
inline int lca(
int a,
int b){
if(depth[a]<
depth[b]) swap(a,b);
for(
int i=
20;i>=
0;i--
){
if(depth[f[a][i]]>=
depth[b])
a=
f[a][i];
}
if(a==b)
return a;
for(
int i=
20;i>=
0;i--
){
if(f[a][i]!=
f[b][i]){
a=f[a][i],b=
f[b][i];
}
}
return f[a][
0];
}
inline void print(
int x){
//打印二进制
if(!x)
return ;
print(x>>
1);
printf("%d",x&
1);
}
int main(){
// freopen("haha.in","r",stdin);
n=read(),m=
read();
for(
int i=
1;i<=m;i++
){
x[i]=read(),y[i]=
read();
e[x[i]].push_back(y[i]);
e[y[i]].push_back(x[i]);
}
for(
int i=
1;i<=n;i++
){
if(!
dfn[i])tarjan(i,i);
}
rebuild();
megumi++
;
for(
int i=
1;i^megumi;i++
){
if(!
vis[i])dfs(i,i);
}
tot=
read();
for(
int i=
1;i<=tot;i++
){
int x,y;
x=read(),y=
read();
int l=
lca(color[x],color[y]);
print(depth[color[x]]-depth[l]+depth[color[y]]-depth[l]+
1);
printf("\n");
}
// fclose(stdin);
return QAQ;
}
转载于:https://www.cnblogs.com/djhsbdb/p/9868545.html
相关资源：数据结构—成绩单生成器
