POJ_3352_Road Construction_割點_割邊

Road Construction

Time Limit: 2000MS        Memory Limit: 65536K

Total Submissions: 10654        Accepted: 5269

Description

It's almost summer time, and that means that it's almost summer construction time! This year, the good people who are

in charge of the roads on the tropical island paradise of Remote Island would like to repair and upgrade the

various roads that lead between the various tourist attractions on the island.

The roads themselves are also rather interesting. Due to the strange customs of the island, the roads are arranged

so that they never meet at intersections, but rather pass over or under each other using bridges and tunnels. In this

 way, each road runs between two specific tourist attractions, so that the tourists do not become irreparably lost.

Unfortunately, given the nature of the repairs and upgrades needed on each road, when the construction company works

 on a particular road, it is unusable in either direction. This could cause a problem if it becomes impossible to

 travel between two tourist attractions, even if the construction company works on only one road at any particular time.

So, the Road Department of Remote Island has decided to call upon your consulting services to help remedy this problem.

 It has been decided that new roads will have to be built between the various attractions in such a way that in the

 final configuration, if any one road is undergoing construction, it would still be possible to travel between any two

  tourist attractions using the remaining roads. Your task is to find the minimum number of new roads necessary.

Input

The first line of input will consist of positive integers n and r, separated by a space, where 3 ≤ n ≤ 1000 is the

 number of tourist attractions on the island, and 2 ≤ r ≤ 1000 is the number of roads. The tourist attractions are

 conveniently labelled from 1 to n. Each of the following r lines will consist of two integers, v and w, separated by

  a space, indicating that a road exists between the attractions labelled v and w. Note that you may travel in either

   direction down each road, and any pair of tourist attractions will have at most one road directly between them.

   Also, you are assured that in the current configuration, it is possible to travel between any two tourist

   attractions.

Output

One line, consisting of an integer, which gives the minimum number of roads that we need to add.

Sample Input

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

Sample Output

Output for Sample Input 1

2

Output for Sample Input 2

*/

/*

題意：

    某個企業想把一個熱帶天堂島變成旅遊勝地，島上有N個旅遊景點，任意2個旅遊景點之間有路徑連通（注意不一定是直接連通）。

而為了給遊客提供更友善的服務，該企業要求道路部門在某些道路增加一些設施。道路部門每次隻會選擇一條道路施工在該條道路施工

完畢前，其他道路依然可以通行。然而有道路部門正在施工的道路，在施工完畢前是禁止遊客通行的。這就導緻了在施工期間遊客

可能無法到達一些景點。為了在施工期間所有旅遊景點依然能夠正常對遊客開放，該企業決定搭建一些臨時橋梁，

使得不管道路部門選在哪條路進行施工，遊客都能夠到達所有旅遊景點。給出當下允許通行的R條道路，

問該企業至少再搭建幾條臨時橋梁，才能使得遊客無視道路部門的存在到達所有旅遊景點？

 給定一個連通的無向圖G，至少要添加幾條邊，才能使其變為雙連通圖。

用Tarjan算法 求解每個low[i]值，然後求解所有的縮點（雙聯通分量個數）。

要添的邊 = （縮點個數+1）/2;

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
const int Max_N = 1002;
int n,m,num;
bool vis[Max_N];
int dfn[Max_N];
int low[Max_N];
int dist[Max_N];
vector<int> G[Max_N];

void init()
{
	int i;
	for(i=0;i<=n;i++)
	{
		G[i].clear();
	}
	memset(dist,0,sizeof(dist));
	memset(vis,false,sizeof(vis));
}

void add_edge(int a,int b)
{
	G[a].push_back(b);
	G[b].push_back(a);
}

void dfs(int x,int father)
{
	int i;
	vis[x] = true;
	num ++ ;
	dfn[x] = num;
	low[x] = num;
	for(i=0;i<G[x].size();i++)
	{
		int v = G[x][i];
		if(vis[v]==false)
		{
			dfs(v,x);
			low[x] = min(low[x],low[v]);
		}
		else if(vis[v]==true && v!=father)
		{
			low[x] = min(low[x],dfn[v]); 
		}
	}
}

int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		int i,j,a,b;
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&a,&b);
			add_edge(a,b);
		}
		num = 0;
		dfs(1,1);
		int res = 0;
		for(i=1;i<=n;i++)
		{
			for(j=0;j<G[i].size();j++)
			{
				if(low[i]!=low[G[i][j]])
				{
					dist[low[i]] ++ ;
				}
			}
		} 
		for(i=1;i<=n;i++)
		{
			if(dist[i]==1)
			{
				res++;
			}
		}
		printf("%d\n",(res+1)>>1);
	}
	return 0;
}