题目链接

395. 冗余路径

为了从 \(F\) 个草场中的一个走到另一个，奶牛们有时不得不路过一些她们讨厌的可怕的树。

奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择。

每对草场之间已经有至少一条路径。

给出所有 \(R\) 条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量，路径由若干道路首尾相连而成。

两条路径相互分离，是指两条路径没有一条重合的道路。

但是，两条分离的路径上可以有一些相同的草场。

对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路。

输入格式

第 \(1\) 行输入 \(F\) 和 \(R\)。

接下来 \(R\) 行，每行输入两个整数，表示两个草场，它们之间有一条道路。

输出格式

输出一个整数，表示最少的需要新建的道路数。

数据范围

\(1 \le F \le 5000\),
\(F-1 \le R \le 10000\)

输入样例：

7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7

输出样例：

2

解题思路

缩点，边双连通分量

无向图的边双连通分量涉及到桥（边）的概念：删除该边后连通块的数量会发生改变。边双连通分量即不含桥的极大连通分量，即删除边双连通分量内的任意一条边后两个端点仍然连通。
求法类似于强连通分量 1174. 受欢迎的牛，假设遍历到 \(x\)，对于另外一个节点 \(y\)，这条边是桥当且仅当 \(dfn[x]<low[y]\)，即 \(y\) 不能跑到 \(x\) 的前面

• 时间复杂度：\(O(n+m)\)

代码

// Problem: 冗余路径
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/397/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=5005,M=20005;
int n,m;
int h[N],e[M],ne[M],cnt;
int dfn[N],low[N],timestamp,dcc_cnt,id[N];
int stk[N],top;
int d[N];
bool is_bridge[N];
void add(int a,int b)
{
	e[cnt]=b,ne[cnt]=h[a],h[a]=cnt++;
}
void tarjan(int x,int from)
{
	dfn[x]=low[x]=++timestamp;
	stk[++top]=x;
	for(int i=h[x];~i;i=ne[i])
	{
		int j=e[i];
		if(!dfn[j])
		{
			tarjan(j,i);
			low[x]=min(low[x],low[j]);
			if(dfn[x]<low[j])
				is_bridge[i]=is_bridge[i^1]=true;
		}
		else if(i!=(from^1))low[x]=min(low[x],dfn[j]);
	}
	if(dfn[x]==low[x])
	{
		dcc_cnt++;
		int y;
		do
		{
			y=stk[top--];
			id[y]=dcc_cnt;
		}while(y!=x);
	}
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
    	int x,y;
    	scanf("%d%d",&x,&y);
    	add(x,y),add(y,x);
    }
    tarjan(1,-1);
    for(int i=0;i<cnt;i++)
    	if(is_bridge[i])d[id[e[i]]]++;
    int res=0;
    for(int i=1;i<=dcc_cnt;i++)
    	if(d[i]==1)res++;
    res=(res+1)/2;
    printf("%d",res);
    return 0;
}

原文地址：http://www.cnblogs.com/zyyun/p/16901034.html