POJ--3352 道路建设

POJ–3352 道路建设

题目描述

输入样例1

10 12
1 2
1 3
1 4
2 5
2 6
5 6
3 7
3 8
7 8
4 9
4 10
9 10

输出样例1

2

输入样例2

3 3
1 2
2 3
1 3

输出样例2

0

题意分析:

题目中的景点相当于图中的点,道路相当于路径,当修一条路时候两个景点无法旅行,所以我们要通过修路来解决这个问题,让即使去掉一条边当前图依旧连通.也就是求在图中添加多少条边从而可以去掉任意边都依旧连通…
易知图中,边双连通分量之间,去掉任意一条边该连通分量依旧是连通的,所以可以求出连通图中边双连通分量的个数,然后缩点.最后统计叶子节点的个数,通过叶子结点获得应该增加多少条边.

解题步骤

如果结点在一个边双连通分量中，则不需要添加边。而连通分量之间需要添加边,因此需要求解连通分量。

1. 样例1中,可求得边连通分量共有4个.样例2中双联通分量只有一个(所以需要添加0条边).

2.将每个双连通分量缩成点.

2. 需要的添加的新路数量，先计算度为1的点数k，则至少添加(k+1)/2边。例如，3个度为1的顶点，需要加两条边，4个度为1的顶点也需要加两条边。因为对于奇数个叶子节点,每两个需要一条边来构成双连通分量.也就是需要(k+1) / 2条边.如果偶数个点.则需要 k /2. 易知 k+1 / 2 与k/2值是一样的.所以都用k+1/2即可

算法设计

参考代码

#include<iostream>
#include<string.h>
using namespace std;
const int maxn = 1000 + 5;
int n, m;
int head[maxn], cnt;
struct Edge
{
   
	int to, next;
}e[maxn << 1];
int low[maxn], dfn[maxn], degree[maxn], num;
void add(int u, int v)
{
   
	e[++cnt].next = head[u];
	e[cnt].to = v;
	head[u] = cnt;
}
void tarjan(int u, int fa)//使用tarjan算法求出每个节点的low和dfn值
{
   
	dfn[u] = low[u] = ++num;
	for (int i = head[u]; i; i = e[i].next)
	{
   
		int v = e[i].to;
		if (v == fa)
			continue;
		if (!dfn[v])
		{
   
			tarjan(v, u);
			low[u] = min(low[u], low[v]);//注:如果是求割点或割边则下边就开始进行判断.
		}
		else
			low[u] = min(low[u], dfn[v]);
	}
}
void init()
{
   
	memset(head, 0, sizeof(head));
	memset(low, 0, sizeof(low));
	memset(dfn, 0, sizeof(dfn));
	memset(degree, 0, sizeof(degree));
	cnt = num = 0;
}

int main()
{
   
	while (cin >> n >> m)
	{
   
		init();
		int u, v;
		while (m--)
		{
   
			cin >> u >> v;
			add(u, v);
			add(v, u);
		}
		tarjan(1, 0);
		for (int u = 1; u <= n; u++)
		{
   
			for (int i = head[u]; i; i = e[i].next)
			{
   
				int v = e[i].to;
				if (low[u] != low[v])//对于每个连通分量命个名(以low命名)然后进行缩点,
				{
   
					degree[low[u]]++;//缩点
				}
			}
		}
		int leaf = 0;
		for (int i = 1; i <= n; i++)//统计节点度数为1的个数
		{
   
			if (degree[i] == 1)
			{
   
				leaf++;
			}
		}
		cout << (leaf + 1) / 2 << endl;
	}
	return 0;
}

题目考点

1.tarjan算法的使用
2.对于双连接图的理解.