自动搬运

查看原文

来自洛谷，原作者为

	SammyChu **

搬运于2025-08-24 21:41:34，当前版本为作者最后更新于2019-06-02 20:15:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

在$[WA]$了$10$次之后，我终于过了这道题……

读完题后思路就已经很明朗了：

1. 找环，缩点
2. 利用$LCA$寻找两点之间碳的个数

但是……找环的过程？由于这是个无向图，所以是不存在强连通分量的。强连通分量是有向图中的定义。对于无向图只有双连通分量。而双连通分量又分两种：

• 点-双连通分量
• 边-双连通分量

从题目描述来看，本题需要把所有的碳环全部缩成一个点。但是由于我对双连通分量的缩点不熟，于是我专门去查看了资料：点-双连通分量的缩点是基于割点的，而边-双连通分量是基于桥的。

问题来了：是写 点-双连通分量 还是 边-双连通分量 呢？仔细查看定义后，我发现：点-双连通分量 缩点后的结构是不符合本题的要求的。因为它缩点后是会把割点看作单独的一个点，而本题是要求把所有的简单环变成一个点，此时这显然是不对的。

至于题解里的各位大佬写的“点-双连通分量”，要么是我学艺不精，没有正确$get$ 点-双连通分量 的缩点的真正定义，要么就是那个不能叫 点-双连通分量 的缩点。不管怎么说，我放弃了写 点-双连通分量 的想法。

$P.S.$

这里仅仅是发表了个人的观点，如有异议欢迎在讨论区指教。个人感觉应该是我理解错了，因为那个感觉是强行把无向图写成了有向图的强连通分量，这当然是正确的，而且十分巧妙，只是说法可能不一样。如有冒犯，请多多包涵。（瑟瑟发抖）

经过一番深思熟虑，我决定写 边-双连通分量。边-双连通分量 的求解方法如下：

1. 找到该图中的所有的桥（删去后使得原图不连通的边）
2. 把桥删掉，此时图中的每一个连通的部分组成一个 边-双连通分量。

然而这种做法有一个巨大的$bug$摆在面前：两点间的重边只能算一条边。而在桥的定义中，一旦有重边的存在，这些重边就都不能叫做桥了。但是在本题中，这是不对的。

解决的办法：去掉重边即可。

重边怎么去掉呢？我想到了三种思路：（我因为太菜了不会写$vector$）

1. 若用邻接表存图，则可利用哈希表的方式，在添加边之前先看有没有这条边存在。但是时间复杂度为$O(n^{2})$，超时。

2. 若采用邻接矩阵存图，则可以$O(1)$去掉重边，但是空间无法承受。

3. 采用双链表存图，并且把所有的边复制一遍，按照按照起点优先，终点其次，编号最后的关键字排序，然后$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)$。

$[AC]$代码如下，其中有注释。

#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;
}

当然，我这种写法其实并不优，复杂度没有其他大佬们的方法优，请谅解！