POJ 3352 Road Construction（边双连通分量）

题目意思：

给定一个无向图，图中没有重边，问添加几条边才能使得无向图变为 边双连通图

本题要点：

1、tarjan算法中，求割边时候，每个点都记录一个时间戳 dfn[i], 和回溯值 low[i]。

有多少个不同的low 值，就有多少个边双连通分量。

2、缩点：

把low值相同的点，看做是一个缩点。用 deg 数组记录每一个缩点的入度。

3、问题转化为：

在缩点树上，添加多少条边，才能使得树变为一个边双连通图。

至少添加边数 = （入度为1的缩点数 + 1） / 2

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 2010;
int n, m, tot, num;
int head[MaxN], ver[MaxN], Next[MaxN], from[MaxN];
int dfn[MaxN], low[MaxN], deg[MaxN];
bool bridge[MaxN];

void add(int x, int y)
{
	ver[++tot] = y, from[tot] = x, Next[tot] = head[x], head[x] = tot;
}

void tarjan(int x, int in_edge)
{
	dfn[x] = low[x] = ++num;
	for(int i = head[x]; i; i = Next[i])
	{
		int y = ver[i];
		if(!dfn[y])
		{
			tarjan(y, i);	
			low[x] = min(low[x], low[y]);
			if(low[y] > dfn[x])
			{
				bridge[i] = bridge[i ^ 1] = true;
			}
		}else if(i != (in_edge ^ 1)){
			low[x] = min(low[x], dfn[y]);		
		}
	}
}

void solve()
{
	memset(deg, 0, sizeof deg);
	//相同 low 值得点看做是一个缩点
	for(int i = 2; i <= tot; ++i)
	{
		int y = ver[i], x = from[i];
		if(low[x] != low[y])
			deg[low[y]]++;
	}
	int cnt = 0;	//入度为1的点
	for(int i = 1; i <= n; ++i)
	{
		if(1 == deg[i])
		{
			++cnt;	
		}
	}
	printf("%d\n", (cnt + 1) / 2);
}

int main()
{
	int x, y;
	while(scanf("%d%d", &n, &m) != EOF)
	{
		tot = 1, num = 0; 
		memset(bridge, false, sizeof bridge);
		memset(head, 0, sizeof head);
		for(int i = 1; i <= m; ++i)
		{
			scanf("%d%d", &x, &y);
			add(x, y);
			add(y, x);
		}
		for(int i = 1; i <= n; ++i)
		{
			if(!dfn[i])
			{
				tarjan(i, 0);
			}
		}
		solve();
	}
	return 0;
}

/*
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

3 3
1 2
2 3
1 3
*/

/*
2
0
*/