Uva 10972 RevolC FaeLoN(邊雙連通分量)

題意：給定一個無向圖，要求把所有的無向邊改成有向邊，并且添加最少的有向邊使得新圖強連通。

分析：無向圖的邊雙轉換成有向圖的話一定可能變成強連通，另一方面所有的強連通去掉邊上的方向後一定都是邊雙（每條邊都保證在一個簡單環中），是以我們隻要把原圖變成一個邊雙就行了，先求出所有邊雙後縮點，手動推算一下發現答案就是縮點後（入讀為1的點個數+1）/2 + 入讀為0的點個數。

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
#define INF 0x3f3f3f3f
#define MAX 2147483647
#define eps 1e-9
#define MAXN 1005
using namespace std;
int n,m,color,dfs_clock,vis[MAXN],pre[MAXN],low[MAXN],d[MAXN];
bool isbri[MAXN][MAXN];
vector<int> G[MAXN];
int dfs(int u,int fa)
{
	low[u] = pre[u] = ++dfs_clock;
	for(int v : G[u])
	 if(!pre[v])
	 {
		low[u] = min(low[u],dfs(v,u));
		if(low[v] > pre[u]) isbri[u][v] = isbri[v][u] = true; 
	 }
	 else if(pre[v] < pre[u] && v != fa) low[u] = min(low[u],pre[v]);
	return low[u];
}
void dfs2(int u)
{
	vis[u] = color;
	for(int v : G[u])
	 if(!isbri[u][v] && !vis[v]) dfs2(v);
} 
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		dfs_clock = color = 0;
		memset(pre,0,sizeof(pre));
		memset(isbri,0,sizeof(isbri));
		memset(vis,0,sizeof(vis));
		memset(d,0,sizeof(d));
		for(int i = 1;i <= n;i++) G[i].clear(); 
		for(int i = 1;i <= m;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			G[x].push_back(y);
			G[y].push_back(x);
		}
		for(int i = 1;i <= n;i++) 
		 if(!pre[i]) dfs(i,-1);
		for(int i = 1;i <= n;i++) 
		 if(!vis[i]) 
		 {
		 	color++;
		 	dfs2(i);
	   	 }
		for(int i = 1;i <= n;i++)
		{
			for(int v : G[i]) 
			 if(isbri[i][v]) d[vis[i]]++;
		}
		int number0 = 0,number1 = 0;
		for(int i = 1;i <= color;i++)
		 if(!d[i]) number0++;
		 else  if(d[i] == 1) number1++;
		if(color == 1) printf("0\n");
		else printf("%d\n",(number1+1)/2+number0);
	}
 }