首页 > 代码库 > POJ 3352 Road Construction POJ 3177 Redundant Paths（边双连通图 Tarjan+缩点）

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

2024-07-17 18:15:02   230人阅读

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;
}


联系
我们