首页 > 其他 > 详细

POJ 3352 Road Construction POJ 3177 Redundant Paths(边双连通图 Tarjan+缩点)

时间:2014-08-15 12:54:58      阅读:306      评论:0      收藏:0      [点我收藏+]

POJ 3352 Road Construction POJ 3177 Redundant Paths(边双连通图 Tarjan+缩点)

ACM

题目地址: 
POJ 3352 Road Construction 
POJ 3177 Redundant Paths

题意: 
问要添加几条边才能使所给无向图图变成边双连通图。

分析: 
边连通度:使无向图G不连通的最少删边数量为其边连通度。 
边双连通图:边连通度大于1的无向图。

首先缩点,让图变成一个DAG。 
现在问题转化为:在树中至少添加多少条边能使图变为双连通图。 
若要使得任意一棵树,在增加若干条边后,变成一个双连通图,那么至少增加的边数 =( 这棵树总度数为1的结点数 + 1 )/ 2。 
其实就是让树的叶子节点都成对相连,可以在纸上画看看就知道了。

代码

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        3352.cpp
*  Create Date: 2014-08-13 15:28:44
*  Descripton:   
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
#define repf(i,a,b) for(int i=(a);i<=(b);i++)

typedef long long ll;

const int N = 5010;

vector<int> G[N];
bool app[N][N], instack[N];
int n, r, u, v;
int dfn[N], low[N], dg[N], tclock;

void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++tclock;
	instack[u] = 1;

	int sz = G[u].size();
	repf (i, 0, sz - 1) {
		int v = G[u][i];
		if (v == fa)
			continue;
		if (!dfn[v]) {
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
		} else if (instack[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
}

void init(int n, int r) {
	memset(app, 0, sizeof(app));
	memset(low, 0, sizeof(low));
	memset(dfn, 0, sizeof(dfn));
	memset(instack, 0, sizeof(instack));
	memset(dg, 0, sizeof(dg));
	repf (i, 1, n) {
		G[i].clear();
	}

	repf (i, 0, r - 1) {
		scanf("%d%d", &u, &v);
		if (!app[u][v]) {
			G[u].push_back(v);
			G[v].push_back(u);
			app[u][v] = app[v][u] = 1;
		}
	}
}

void solve() {
	tarjan(1, -1);
	repf (u, 1, n) {
		int sz = G[u].size();
		repf (i, 0, sz - 1) {
			int v = G[u][i];
			if (low[u] != low[v])
				dg[low[u]]++;
		}
	}

	int cnt = 0;
	repf (i, 1, n) {
		if (dg[i] == 1) {
			cnt++;
		}
	}

	printf("%d\n", (cnt + 1) / 2);
}

int main() {
	while (~scanf("%d%d", &n, &r)) {
		init(n, r);
		solve();
	}
	return 0;
}


POJ 3352 Road Construction POJ 3177 Redundant Paths(边双连通图 Tarjan+缩点),布布扣,bubuko.com

POJ 3352 Road Construction POJ 3177 Redundant Paths(边双连通图 Tarjan+缩点)

原文:http://blog.csdn.net/hcbbt/article/details/38582473

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!