2019-09-10

poj-3352-Road-Construction 不带重边的边bcc

缘起

本题参考了题解【1】. 的确讲的很透彻~

分析

某个企业想把一个热带天堂岛变成旅游胜地，岛上有N个旅游景点，任意2个旅游景点之间有路径连通
（注意不一定是直接连通）。而为了给游客提供更方便的服务，该企业要求道路部门在某些道路增加一些设施。
道路部门每次只会选择一条道路施工，在该条道路施工完毕前，其他道路依然可以通行。
然而有道路部门正在施工的道路，在施工完毕前是禁止游客通行的。这就导致了在施工期间游客可能无法到达一些景
点。为了在施工期间所有旅游景点依然能够正常对游客开放，该企业决定搭建一些临时桥梁，
使得不管道路部门选在哪条路进行施工，游客都能够到达所有旅游景点。给出当下允许通行的R条道路，问该企业至少
再搭建几条临时桥梁，才能使得游客无视道路部门的存在到达所有旅游景点？
本题输入保证两点之间无重边.而且保证是无向连通图

【输入】
给出n和r（3 ≤ n ≤ 1000是岛屿的个数, 2 ≤ r ≤ 1000 是边的条数.） 然后下面r行都是2个正整数v和w,表示一条
v和w之间有一条边.

【输出】
最少加几条边可以使得原图变成边bcc.

【样例输入】
Sample Input 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

Sample Input 2
3 3
1 2
2 3
1 3

【样例输出】
Output for Sample Input 1
2

Output for Sample Input 2
0

【限制】
2s

本题的建模其实是十分简单的——就是问你一个无向连通图（无重边），问最少加几条边可以原图变成边bcc.

这种题目一般都要求出边bcc，然后缩点. 然后形成无向树之后进行判断. 如果形成无向树之后，显然只需要将叶子们（即deg为1的点)两两配对连接起来即可. 所以答案是

1	(leaf+1)>>1

形象的图解为(注意，两个边bcc之间最多连一条边，这是显然的，不然就在同一个边bcc中了呀~)

图1

加1是处于考虑叶子的数量为奇数的情况.

本题是边bcc的第一题. 所以要讲清楚一些问题.

有重边对于求割点以及点bcc有影响吗?

答: 没有. 因为判断割点是根据不通过父节点回到的最早时间戳. 这和有无重边无关.

求割边（即桥）的low数组的意义是什么? 它和割点的low数组的意义可以一样吗?

答: 求割点的low数组的意义是

low[i]是i不经过它的父节点能回到的最早的时间戳. 而

求割边的low数组的意义是

low[i]是i不经过来路能回到的最早的时间戳. 所以原先写的【4】和【5】求割边以及边bcc的算法是错误的(进而啊哈算法中求割边的算法也有问题).

其实你仔细品味一下上面的定义，是非常具备对称美的. 而且最重要的事情是非常复合直观——求割点我自然是不允许跨过父节点，求割边我自然是希望不能跨过原先来的边啦~

能不能一样要看实际题目以及使用low数组的时机（因为low数组是在dfs的时候求得的.）但是使用”不能跨越来边回到的最早时间戳是一定不会出错的”. 例如本题的解法是跑完tarjan算法之low数组值一样的，一定在同一个边bcc中. 如果采用”low的意义是不经过父节点能回到的最早的时间戳”的话，则就是错误的. 不需要有重边都能有反例. 例如下图

跑完tarjan算法之后low[1]=low[2]=low[3]=1, low[4]=low[5]=3. 那么1、2、3就在一个边bcc中，4和5就在一个边bcc中咯? 这不胡扯吗? 显然1、2、3、4、5都应该在同一个边bcc中.

图2

对于有重边的情形，割边和边bcc的求法有什么影响吗?

答: 如果你使用low数组的意义为——low[i]是不经过来路能回到的最早时间戳. 则没有影响. 因为

图3

对于上图, 1和2之间存在重边. 则low[1]和low[2]在跑完tarjan算法之后是一样的，都是1（不会出现【1】说的——对于带重边的无向图，low不同亦可能在同一个边bcc中, 这是因为【1】中对low的定义是不经过父节点回到的最早时间戳, 也是我认为错误的做法——虽然它的代码可以ac）. 对于图2，也是一样，跑完tarjan算法得到的low都是1. 所以我们就会发现求点bcc（即块）和求边bcc的不同之处.——

首先求割点的话，它的low是一定要是”不经过父节点能回到的最早时间戳”，而不能是不经过来路能回到的时间戳. 否则反例是显然的，图2就是. 如果low是”不经过来路能回到的最早时间戳”的话, 则跑tarjan的过程中，4和5的low就都能达到1了, 则就会得出图中不存在割点的错误结论. 其次, 求块的时候，不能依据跑完tarjan 的low数组——low一样就在一个块中. 因为这样的话，图2中1,2,3就在一个块中，而4,5,在另一个块中（因为low在tarjan的过程中会变的，low[3]由3变成了1，实际上是两个块共用了顶点3），但是这样是不正确的, 求块只能在tarjan的过程中遇到一组就处理一组, 就像著名的【6】一样.

而求边bcc呢? 它的low一定要用”不经过来路最早能回到的时间戳”. 则边bcc就好求太多了——

求边bcc其实比求点bcc要容易. 容易的情形是无重边的时候, 因为无重边的时候, 就可以跑一遍tarjan之后low数组自动帮我们缩好点了. 但是对于有重边的情形, 跑完tarjan之后,low数组并没有帮我们缩好点(即并不是low值一样等价于在同一个边bcc中,因为会出现low值不一样但是在同一个边bcc的情形, 例如 1-6有8条边
1 2
2 3
3 4
4 5
2 6
6 2
1 3
4 7) 你会发现low[6]跑完只能到2.但是1 2 3 6显然在同一个边bcc中. 所以有重边的边bcc求法依旧要和点bcc那样老老实实的碰到割边就收割那种做法来做, 具体见hdu 4612(【2】)这道题目
而对于点bcc,不论是否有重边都是不能使用low数组一样就在一个点bcc来做的.原因刚刚说了——low在跑tarjan算法的时候会变的. 当然,如果仅仅是求割边的话（不论有无重边）, 就不用做这些了,只需要出现割边的时候判断一下就好了,详见 lightoj-1026（【7】） zoj-2588（【3】）这两道题目

割点以及块的算法在之前的文章以及【6】中应验了. 关于割边以及边bcc的论述将在【2】、【3】、【7】中进行验证.

说了这么多，回到本题. 本题首先要求出边bcc. 就像上面说的一样——我们使用low的意义是不从来路能回到的最早时间戳. 因为本题确保输入无重边,所以可以基于low数组进行缩点. 即最后low一样的就在同一个边bcc中. 这样就缩点了, 然后重构缩点后的图，统计叶子数量leaf，然后(leaf+1)>>1 就是答案

//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
//#define LOCAL

struct Edge
{
	int to, id; // to是边的端点, id是边的id
	Edge(int to, int id):to(to), id(id){}
};

int n,r,timestamp[1005],low[1005],t,deg[1005];
vector<Edge> g[1005];
typedef vector<Edge>::iterator vit;

void dfs(int cur ,int fa) // fa的含义不再是求割点中的父节点, 而是到来的路的编号
{
	timestamp[cur] = low[cur] = ++t;
	for (vit x = g[cur].begin(); x!=g[cur].end(); x++)
	{
		if (!timestamp[x->to])
		{
			dfs(x->to, x->id);
			low[cur] = min(low[cur], low[x->to]); // 不需要判断割边,题目无此需求
		}
		else if (x->id!=fa) // 如果不是来的路,但是x->to已经搜过了
		{
			low[cur] = min(low[cur], timestamp[x->to]);
		}
	}
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n, &r);
	for(int id = 1; id<=r; id++)
	{
		int a,b;
		scanf("%d%d", &a, &b);
		g[a].push_back(Edge(b, id)), g[b].push_back(Edge(a, id));
	}
	dfs(1,0); // 跑tarjan
	for (int i = 1; i<=n; i++)
	{
		for (vit x = g[i].begin(); x!=g[i].end(); x++)
		{
			if (low[i]!=low[x->to]) // 如果边的两个端点不在一个边bcc中的话, 即一个在low[i]这个边bcc中, 一个在low[x->to]这个边bcc中
			{
				deg[low[i]]++; // 注意, 因为x->to也会作为i做++的, 所以这里不需要写 deg[x->to]++了
			}
		}
	}
	int leaf = 0;
	for (int i = 1; i<=n;i++)
	{
		if (deg[i]==1)
		{
			leaf++;
		}
	}
	printf("%d\n", (leaf+1)>>1);
	return 0;
}