自动搬运

查看原文

来自洛谷，原作者为

	说好不哭 **

搬运于2025-08-24 21:42:24，当前版本为作者最后更新于2019-04-01 01:09:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解 P2860 【冗余路径】

注意：因为已有题解讲明白了题意和思路，所以我就不在此重复了，我只是想说明一下最简单清晰的一个方法——这就是一个求双联通分量的模板（当然，你也可以理解为无向图缩点）

所以，打一遍模板即可。当然，对于这个模板，我想要讲的清楚一些。

对于无向图的缩点，由于是无向图，所以要从u到v建一条边，又要从v到u建一条边，但是，在tarjan时会有两条边重复，这是一个麻烦，而且，还不得不建两条边，这该怎么办呢？

解决的方法就是，当同一条无向边的两条有向边的其中一条走过时，把另一条同时赋值为走过，这就要用到一个神奇的公式，^1。 举例来说，0^1=1,1^1=0; 2^1=3,3^1=2; 4^1=3,3^1=4......相信大家已经都发现了规律。而建边的时候，一条无向边的两条有向边刚好相差1，这不很OK嘛？问题解决了。

不过要注意，我的cnt，就是边的初始值，赋值为1，这是用来凑数字的。所以边，是从第2，3条；第4,5条......这样下去的（对于0,1条，因为自己代码习惯，我就直接从2开始了，0,1条加进去应该也可以，你想试的话也可以试试）

其余地方，就和有向图的缩点完全一样了。

#include <bits/stdc++.h>
using namespace std;
const int N=5e3+5,M=1e4+5;
int n,m,vis[M<<1],du[N],ans;
int cnt=1,head[N],u[M],v[M];
int now,top,col,dfn[N],low[N],sta[N],color[N];
struct edge{int next,to;}e[M<<1];

inline void add(int u,int v)
{
	cnt++;
	e[cnt].next=head[u];
	e[cnt].to=v;
	head[u]=cnt;
	cnt++;
	e[cnt].next=head[v];
	e[cnt].to=u;
	head[v]=cnt;
}

inline void tarjan(int u)
{
	dfn[u]=low[u]=++now;	
	sta[++top]=u;
	for (register int i=head[u]; i; i=e[i].next)
	if (!vis[i])
	{
	vis[i]=vis[i^1]=1;
		if (!dfn[e[i].to])
		{
			tarjan(e[i].to);	
			low[u]=min(low[u],low[e[i].to]);
		}
		else low[u]=min(low[u],dfn[e[i].to]);
	}
	if (low[u]==dfn[u])
	{
		color[u]=++col;	
		while (sta[top]!=u) color[sta[top]]=col,top--;
		top--;
	}
}

int main(){
memset(head,0,sizeof(head));
memset(dfn,0,sizeof(head));
//下面过程如果不懂，看前面的几篇题解吧
	scanf("%d%d",&n,&m);
	for (register int i=1; i<=m; ++i) scanf("%d%d",&u[i],&v[i]),add(u[i],v[i]);
	for (register int i=1; i<=n; ++i) if (!dfn[i]) tarjan(i);
	for (register int i=1; i<=m; ++i) if (color[u[i]]!=color[v[i]]) du[color[u[i]]]++,du[color[v[i]]]++;
	for (register int i=1; i<=col; ++i) if (du[i]==1) ans++;
printf("%d\n",ans+1>>1);
return 0;	
}

代码可以当作模板收藏。