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