POJ 3177 redundant paths POJ 3352 road construction (dual connection)

Hello everyone , I meet you again , I'm the king of the whole stack

POJ 3177 Redundant Paths

POJ 3352 Road Construction

Topic link

The question ： The two questions are the same . A piece of code can hand in . Given a connected undirected graph , How many edges can make a graph become a biconnected graph

Ideas ： Find biconnection first . Shrink a little . The calculated penetration is 1 The number of , then （ Number + 1） / 2 That's the answer. （ This problem can be solved because there is only one connected block , Suppose there are more than one , You can't do this ）

Code ：

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

Copy

Copyright notice ： This article is the original article of the blogger , Blog , Do not reprint without permission .

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/116888.html Link to the original text ：https://javaforall.cn