信息学奥赛一本通 1520：【 例 1】分离的路径 | 洛谷 P2860 [USACO06JAN]Redundant Paths G

【题目链接】

ybt 1520：【 例 1】分离的路径
洛谷 P2860 [USACO06JAN]Redundant Paths G

【题目考点】

1. 图论：割边（桥） 边双连通分量

【解题思路】

每个草场是一个顶点，草场之间的双向路是无向边，该图是无向图。建新的道路，就是添加边。
“每对草场之间已经有至少一条路径”，表示该图是连通图。
“同一对草场之间，可能已经有两条不同的道路”，表示图中可能有重边。
“使每一对草场之间都会至少有两条相互分离的路径”，而且“两条路径相互分离，是指两条路径没有一条重合的道路”，也就是希望最后图中任何两个顶点之间都有两条边不重复的路径，这样的图就是边双连通图。
求的是最少增加的路径的数目。
该题抽象后可以描述为：给定一个无向图，求最少添加几条边可以使该图变为边双连通图。

如果两顶点处于一个边双连通分量中，那么这两顶点之间就一定不需要添加边，因为两顶点之间已经存在两条边不重复的路径。因此只有两顶点在不同的边双连通分量中，才需要考虑是否需要在两顶点之间添加边。
这里可以考虑将图中每个边双连通分量变为一个顶点，也就是“缩点”，缩点后的图一定不存在双连通分量，是无环连通图，也就是树。

反证：如果缩点后存在环，那么环上多个顶点处于一个双连通分量中，在原图中该环连接的所有双连通分量应该同属于一个双连通分量，应该缩为一个点而不是多个点。

考虑要想使缩点后的树变为双连通图，需要添加最少多少条边。
树上任意两顶点连线后，就会形成一个环，该环就是一个双连通分量。
由于环上的顶点都是度为2的顶点，因此树上叶子结点，也就是度为1的顶点要想处于一个环上，必须在度为1的顶点上连接新的边，使该顶点度变为2。
因此每次添加一条边连接两个度为1的顶点，让这两个顶点在树上的路径加上新的边形成一个环。
每两个度为1的顶点需要添加一条边，如果剩下单独一个顶点，也需要在该顶点上增加一条到其它顶点的边。
如果叶子结点数量为$d$，那么需要添加边的数量为$\lceil \frac{d}{2}\rceil$，也就是$\frac{d+1}{2}$

【题解代码】

解法1：Tarjan算法直接求边双连通分量

#include <bits/stdc++.h>
using namespace std;
#define N 5005
int n, m, fa[N], ebc[N], en, deg[N];
vector<int> edge[N];
int dfn[N], low[N], ts;
stack<int> stk;
void tarjan(int u)
{
	int t, fromEdge = 0;//fromEdge：从fa[u]到u的边的数量 
	dfn[u] = low[u] = ++ts;
	stk.push(u);
	for(int v : edge[u])
	{
		if(dfn[v] == 0)
		{
			fa[v] = u;
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if(v != fa[u] || ++fromEdge > 1)//如果fromEdge==2，那么(u, fa[u])存在重边，更新low[u]后可以保证(u,fa[u])不是桥 
			low[u] = min(low[u], dfn[v]);
	}
	if(dfn[u] == low[u])
	{
		en++;
		do
		{
			t = stk.top();
			stk.pop();
			ebc[t] = en;
		}while(t != u);
	}
}
int main()
{
	int f, t, degOneCt = 0;
	cin >> n >> m;
	for(int i = 1; i <= m; ++i)
	{
		cin >> f >> t;
		edge[f].push_back(t);
		edge[t].push_back(f);
	}
	for(int v = 1; v <= n; ++v)	if(dfn[v] == 0)
		tarjan(v);
	for(int u = 1; u <= n; ++u)
		for(int v : edge[u]) if(ebc[v] != ebc[u])
			deg[ebc[v]]++, deg[ebc[u]]++;
	for(int i = 1; i <= en; ++i)//<u, v>, <v, u>统计两次，顶点的度应该除以2 
		deg[i] /= 2;
	for(int i = 1; i <= en; ++i) if(deg[i] == 1)//统计度为1的双连通分量的数量 
		degOneCt++;
	cout << (degOneCt+1)/2;
	return 0;
}

解法2：Tarjan算法先求桥，再求双连通分量

#include <bits/stdc++.h>
using namespace std;
#define N 5005
int n, m, fa[N], ebc[N], en, deg[N];
vector<int> edge[N];
int dfn[N], low[N], ts;
bool bridge[N], vis[N];//bridge[i]：(i, fa[i])是否是桥
bool isBridge(int u, int v)
{
	return fa[u] == v && bridge[u] || fa[v] == u && bridge[v];
}
void tarjan(int u)
{
	int t, fromEdge = 0;//fromEdge：从fa[u]到u的边的数量 
	dfn[u] = low[u] = ++ts;
	for(int v : edge[u])
	{
		if(dfn[v] == 0)
		{
			fa[v] = u;
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if(dfn[u] < low[v])
				bridge[v] = true;//(u,v)是桥 
		}
		else if(v != fa[u] || ++fromEdge > 1)//如果fromEdge==2，那么(u, fa[u])存在重边，更新low[u]后可以保证(u,fa[u])不是桥 
			low[u] = min(low[u], dfn[v]);
	}
}
void dfs(int u)
{
	vis[u] = true;
	ebc[u] = en;
	for(int v : edge[u]) if(!vis[v] && !isBridge(u, v))
		dfs(v);
}
int main()
{
	int f, t, degOneCt = 0;
	cin >> n >> m;
	for(int i = 1; i <= m; ++i)
	{
		cin >> f >> t;
		edge[f].push_back(t);
		edge[t].push_back(f);
	}
	for(int v = 1; v <= n; ++v)	if(dfn[v] == 0)
		tarjan(v);
	for(int v = 1; v <= n; ++v) if(!vis[v])
	{
		++en;
		dfs(v);	
	}
	for(int u = 1; u <= n; ++u)
		for(int v : edge[u]) if(ebc[v] != ebc[u])
			deg[ebc[v]]++, deg[ebc[u]]++;
	for(int i = 1; i <= en; ++i)//<u, v>, <v, u>统计两次，顶点的度应该除以2 
		deg[i] /= 2;
	for(int i = 1; i <= en; ++i) if(deg[i] == 1)//统计度为1的双连通分量的数量 
		degOneCt++;
	cout << (degOneCt+1)/2;
	return 0;
}