题解 P2783 【有机化学之神偶尔会做作弊】
SammyChu
·
·
题解
前言
在[WA]了10次之后，我终于过了这道题……
读完题后思路就已经很明朗了：
- 找环，缩点
- 利用LCA寻找两点之间碳的个数
但是……找环的过程？由于这是个无向图，所以是不存在强连通分量的。强连通分量是有向图中的定义。对于无向图只有双连通分量。而双连通分量又分两种：
从题目描述来看，本题需要把所有的碳环全部缩成一个点。但是由于我对双连通分量的缩点不熟，于是我专门去查看了资料：点-双连通分量的缩点是基于割点的，而边-双连通分量是基于桥的。
问题来了：是写 点-双连通分量 还是 边-双连通分量 呢？仔细查看定义后，我发现：点-双连通分量 缩点后的结构是不符合本题的要求的。因为它缩点后是会把割点看作单独的一个点，而本题是要求把所有的简单环变成一个点，此时这显然是不对的。
至于题解里的各位大佬写的“点-双连通分量”，要么是我学艺不精，没有正确get 点-双连通分量 的缩点的真正定义，要么就是那个不能叫 点-双连通分量 的缩点。不管怎么说，我放弃了写 点-双连通分量 的想法。
P.S.
这里仅仅是发表了个人的观点，如有异议欢迎在讨论区指教。个人感觉应该是我理解错了，因为那个感觉是强行把无向图写成了有向图的强连通分量，这当然是正确的，而且十分巧妙，只是说法可能不一样。如有冒犯，请多多包涵。（瑟瑟发抖）
经过一番深思熟虑，我决定写 边-双连通分量。边-双连通分量 的求解方法如下：
- 找到该图中的所有的桥（删去后使得原图不连通的边）
- 把桥删掉，此时图中的每一个连通的部分组成一个 边-双连通分量。
然而这种做法有一个巨大的bug摆在面前：两点间的重边只能算一条边。而在桥的定义中，一旦有重边的存在，这些重边就都不能叫做桥了。但是在本题中，这是不对的。
解决的办法：去掉重边即可。
重边怎么去掉呢？我想到了三种思路：（我因为太菜了不会写vector）
- 若用邻接表存图，则可利用哈希表的方式，在添加边之前先看有没有这条边存在。但是时间复杂度为O(n^{2})，超时。
- 若采用邻接矩阵存图，则可以O(1)去掉重边，但是空间无法承受。
-
采用双链表存图，并且把所有的边复制一遍，按照按照起点优先，终点其次，编号最后的关键字排序，然后O(m)判重。总时间复杂度：O(m\cdot log_{2}m)，可行。
注意，一定要按照起点，终点，编号的关键字，这样才能保证相同的边相邻。至于为什么要在最后加一个编号，是因为一条无向边是当作两条有向边存的，如果编号从2开始，则一条边 e 的对应边为 e xor 1 。必须要在最后的关键字中加入编号，才能保证前后属于一条无向边的两条有向边是一一对应的。比如前面有两个 3 -> 10 ，编号为 6 、9 ；后面有两个 10 -> 3 ，编号为 8 、7 ，没有一 一对应，去重后就会出错。（这个错我查了一下午，心酸）
至于去重，直接用双链表就可以了。
接下来是缩点。去掉桥后，每一个连通块里的所有点标记上同一个颜色，然后查看所有边，把两条边的两点的颜色连起来重新建图。缩完点后图就变成了一棵树，随便指定一个点为根，跑LCA就行了。我用的是倍增，复杂度为O(n\cdot log_{2}n)。
最后统计出答案后转为二进制即可，总时间复杂度O(m\cdot log_{2}m+tot\cdot n\cdot log_{2}n)。
```cpp
#include<bits/stdc++.h>
using namespace std;
inline void read(int &x)//读入优化
{
int w=x=0;
char ch=0;
while(ch<'0'||'9'<ch)
w|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9')
x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
x=w?-x:x;
}
const int N=1e5,M=5e5;//怒开10倍
//<吐槽>：
//感觉最后一个点超出了题目描述的数据范围
struct Edge
{
int u,v;
}E[M<<1|1],e[M<<1|1];
struct node
{
int no,u,v;
}cop[M<<1|1];
queue<int> q;
int last=1,fst[N+1],nxt[M<<1|1],bef[M<<1|1];//原图
int num,head[N+1],to[M<<1|1];//缩点图
int n,m,dep,dfn[N+1],low[N+1];//tarjan
int tot,cnt,typ[N+1]; //缩点
bool flag[M<<1|1],bri[M<<1|1],vis[N+1],rvis[N+1];//重边 , 桥 , 缩点
int lg2[N+1],as[25][N+1],depth[N+1];//lca
void add(int x,int y)
{
E[++last]=(Edge){x,y};
bef[fst[x]]=last,nxt[last]=fst[x],fst[x]=last;//使用双链表便于删边
cop[last]=(node){last,x,y};
}
bool operator<(const node &x,const node &y)//重载运算符以便于排序删边
{
if(x.u!=y.u)
return x.u<y.u;
if(x.v!=y.v)
return x.v<y.v;
return x.no<y.no;
}
void del(int x)//利用双链表删边
{
flag[x]=1;
if(bef[x])
nxt[bef[x]]=nxt[x];
else
{
int y=E[x].u;
fst[y]=nxt[x];
}
}
void tarjan(int x,int e)//找桥
{
dfn[x]=low[x]=++dep;
for(int i=fst[x];i;i=nxt[i])
{
int y=E[i].v;
if(i==(e^1))
continue;
if(!dfn[y])
{
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(low[y]>dfn[x])
bri[i]=bri[i^1]=1;//桥的判定法则
}
else
low[x]=min(low[x],dfn[y]);
}
}
void run(int x)//遍历找连通块
{
vis[x]=1;
q.push(x);
for(int i=fst[x];i;i=nxt[i])
{
int y=E[i].v;
if(!vis[y]&&!bri[i])
run(y);
}
}
void radd(int x,int y)//重新建图
{
e[++num]=(Edge){x,y};
to[num]=head[x],head[x]=num;
}
void dfs(int x,int fa)//lca预处理
{
rvis[x]=1,depth[x]=depth[fa]+1,as[0][x]=fa;
for(int i=1;i<=lg2[depth[x]]+1;++i)
as[i][x]=as[i-1][as[i-1][x]];
for(int i=head[x];i;i=to[i])
{
int y=e[i].v;
if(!rvis[y]&&y!=fa)
dfs(y,x);
}
}
int lca(int x,int y)//倍增求lca
{
if(depth[x]<depth[y])
swap(x,y);
for(int i=lg2[depth[x]]+1;i>=0;--i)
{
if(depth[as[i][x]]>=depth[y])
x=as[i][x];
if(x==y)
return x;
}
for(int i=lg2[depth[x]]+1;i>=0;--i)
if(as[i][x]!=as[i][y])
x=as[i][x],y=as[i][y];
return as[0][x];
}
void print(int x)
{
if(x==0)
{
printf("0");
return;
}
if(x==1)
{
printf("1");
return;
}
print(x>>1);
printf("%d",x%2);
}
int main()
{
read(n),read(m);
for(int i=1;i<=m;++i)
{
int a,b;
read(a),read(b);
if(a!=b)
add(a,b),add(b,a);
}
sort(cop+2,cop+last+1);//排序去重边
for(int i=3;i<=last;++i)
if(cop[i].u==cop[i-1].u&&cop[i].v==cop[i-1].v)
del(cop[i].no);
for(int i=1;i<=n;++i)
if(!dfn[i])
tarjan(i,1);
for(int i=1;i<=n;++i)
if(!vis[i])
{
run(i);
++cnt;
while(!q.empty())//利用队列存储连通块
{
typ[q.front()]=cnt;
q.pop();
}
}
for(int i=2;i<=last;++i)
{
if(flag[i])
continue;//不要忘了去掉重边
int a=E[i].u,b=E[i].v;
a=typ[a],b=typ[b];
if(a!=b)
radd(a,b),radd(b,a);
}
for(int i=2;i<=cnt;++i)
lg2[i]=lg2[i>>1]+1;
dfs(1,0);
read(tot);
while(tot--)
{
int a,b;
read(a),read(b);
a=typ[a],b=typ[b];
int c=lca(a,b);
int ans=depth[a]+depth[b]-(depth[c]<<1)+1;//计算碳的个数，记得+1
print(ans);
printf("\n");
}
return 0;
}
```
当然，我这种写法其实并不优，复杂度没有其他大佬们的方法优，请谅解！