POJ 3177 Redundant Paths

POJ 3352 Road Construction

题意：两题一样的。一份代码能交。给定一个连通无向图，问加几条边能使得图变成一个双连通图

思路：先求双连通。缩点后。计算入度为1的个数，然后（个数 + 1） / 2 就是答案（这题因为是仅仅有一个连通块所以能够这么搞，假设有多个，就不能这样搞了）

代码：

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 1005;const int M = 20005;int n, m;struct Edge {	int u, v, id;	bool iscut;	Edge() {}	Edge(int u, int v, int id) {		this->u = u;		this->v = v;		this->id = id;		this->iscut = false;	}} edge[M];int first[N], next[M], en;void add_edge(int u, int v, int id) {	edge[en] = Edge(u, v, id);	next[en] = first[u];	first[u] = en++;}void init() {	en = 0;	memset(first, -1, sizeof(first));}int pre[N], dfn[N], dfs_clock, bccno[N], bccn;void dfs_cut(int u, int id) {	pre[u] = dfn[u] = ++dfs_clock;	for (int i = first[u]; i + 1; i = next[i]) {		if (edge[i].id == id) continue;		int v = edge[i].v;		if (!pre[v]) {			dfs_cut(v, edge[i].id);			dfn[u] = min(dfn[u], dfn[v]);			if (dfn[v] > pre[u])				edge[i].iscut = edge[i^1].iscut = true;		} else dfn[u] = min(dfn[u], pre[v]);	}}void find_cut() {	dfs_clock = 0;	memset(pre, 0, sizeof(pre));	for (int i = 1; i <= n; i++)		if (!pre[i]) dfs_cut(i, -1);}void dfs_bcc(int u) {	bccno[u] = bccn;	for (int i = first[u]; i + 1; i = next[i]) {		if (edge[i].iscut) continue;		int v = edge[i].v;		if (bccno[v]) continue;		dfs_bcc(v);	}}void find_bcc() {	bccn = 0;	memset(bccno, 0, sizeof(bccno));	for (int i = 1; i <= n; i++) {		if (!bccno[i]) {			bccn++;			dfs_bcc(i);		}	}}int du[N];int main() {	while (~scanf("%d%d", &n, &m)) {		int u, v;		init();		for (int i = 0; i < m; i++) {			scanf("%d%d", &u, &v);			add_edge(u, v, i);			add_edge(v, u, i);		}		find_cut();		find_bcc();		memset(du, 0, sizeof(du));		for (int i = 0; i < en; i += 2) {			if (!edge[i].iscut) continue;			int u = bccno[edge[i].u], v = bccno[edge[i].v];			if (u == v) continue;			du[u]++; du[v]++;		}		int cnt = 0;		for (int i = 1; i <= bccn; i++)			if (du[i] == 1) cnt++;		printf("%d\n", (cnt + 1) / 2);	}	return 0;}

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116888.html原文链接：https://javaforall.net