HDU 4612 Warm up / 边双连通分量

求建一条路后 最小的桥的数量

缩点 形成一棵树 每条边都是桥 求出这棵树的直径 在树的直径2端建一条边是最优的 这样可以使直径上的桥都去掉

有重边 重边不能算一条 要多次算

做tarjan时 对于u-v 的一条边 那么在枚举v的边的时候 如果第一次遇到fa 就continue 因为重边要算上去啊 第一次不算是因为是无向图

而且要手动扩栈啊

#pragma comment(linker, "/STACK:102400000,102400000")  
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 200010;

vector <int> G[maxn];
vector <int> G2[maxn];
bool vis[maxn];
int dis[maxn];
int pre[maxn];
int low[maxn];
int sccno[maxn];
int dfs_clock;
int scc_cnt;
stack <int> S;
int n, m;
int leaf;
int p;
int bri;
void dfs(int u, int fa)
{
	int flag = 0;
	pre[u] = low[u] = ++dfs_clock;
	S.push(u);
	for(int i = 0; i < G[u].size(); i++)
	{
		int v = G[u][i];
		if(v == fa && !flag)
		{
			flag++;
			continue;
		}
		if(!pre[v])
		{
			dfs(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] > pre[u])
				bri++;
		}
		else
			low[u] = min(low[u], pre[v]);
	}
	if(low[u] == pre[u])
	{
		scc_cnt++;
		while(1)
		{
			int x = S.top();
			S.pop();
			sccno[x] = scc_cnt;
			if(x == u)
				break;
		}
	}
}
void find_scc()
{
	dfs_clock = scc_cnt = bri = 0;
	memset(sccno, 0, sizeof(sccno));
	memset(pre, 0, sizeof(pre));
	for(int i = 1; i <= n; i++)
		if(!pre[i])
			dfs(i, -1);
}

void BFS(int s)
{
	memset(vis, 0, sizeof(vis));
	memset(dis, 0, sizeof(dis));
	queue <int> Q;
	Q.push(s);
	vis[s] = true;
	while(!Q.empty())
	{
		int u = Q.front();
		Q.pop();
		for(int i = 0; i < G2[u].size(); i++)
		{
			int v = G2[u][i];
			if(vis[v])
				continue;
			vis[v] = true;
			dis[v] = dis[u] + 1;
			//printf("%d\n", dis[v]);
			if(leaf < dis[v])
			{
				p = v;
				leaf = dis[v];
			}
			Q.push(v);
		}
	}
}
int main()
{
	while(scanf("%d %d", &n, &m) && (n+m))
	{
		for(int i = 1; i <= n; i++)
		{
			G[i].clear();
			G2[i].clear();
		}
		while(m--)
		{
			int u, v;
			scanf("%d %d", &u, &v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		find_scc();
		//下面是重新建图 也可以根据找出来的桥构图 桥的2个点分别属于2个双连通分量 
		for(int i = 1; i <= n; i++)
		{
			for(int j = 0; j < G[i].size(); j++)
			{
				int v = G[i][j];
				if(sccno[i] != sccno[v])
				{
					G2[sccno[i]].push_back(sccno[v]);
					G2[sccno[v]].push_back(sccno[i]);
				}
			}
		}
		//for(int i = 0; i < G2[2].size(); i++)
		//printf("%d\n", G2[2][i]);
		//printf("%d\n", G2[2].size());
		leaf = 0;
		BFS(1);//2次BFS找出树的最大距离 即树的直径 在树的直径2端建一条边是最优的 
		BFS(p);
		//printf("%d\n", bri);
		//printf("%d\n", leaf);
		printf("%d\n", bri - leaf);
	}
	return 0;
}

HDU 4612 Warm up / 边双连通分量

原文：http://blog.csdn.net/u011686226/article/details/19418979