POJ - 3352 Road Construction

傳送門

題意： 使圖上任意兩點至少存在兩條邊不重複的路， 至少要添加多少條邊；

将每個邊雙連通圖收縮成一個點，這樣就形成了一棵樹，需要添加

條邊（leaf葉子節點數）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 2e3+100;
int n, m;
struct Edge{
	int to, next;
	bool cut;
	Edge () {}
	Edge (int to, int next,bool cut) : to(to), next(next), cut(cut){
	}
}e[N];
int head[N], tot;
void addEdge (int u, int v) {
	e[tot] = Edge (v, head[u], false);
	head[u] = tot++;
}

int low[N];//low[i] 表示i 及 i 後代最早能連回的最早祖先的時間戳
int dfn[N]; //dfn[i] 表示i 的時間戳 
int stack[N];
int belong[N];//belong[i]表示點i 屬于連通分量belong[i] 
int index, top, ecc, bridge;//時間戳、棧頂、邊連通分量數、橋數 
bool instack[N];//instack[i]點i 在棧中 
void tarjan (int u, int fa) {
	int v;
	low[u] = dfn[u] = ++index;
	stack[top++] = u;
	instack[u] = true;
	int pre_cnt = 0;
	for (int i = head[u]; i != -1; i = e[i].next) {
		v = e[i].to;
		if(v == fa && pre_cnt == 0) {//除去v的祖先 
			pre_cnt++; continue;
		}
		if (!dfn[v]) {
			tarjan(v, u);
			low[u] = min (low[u], low[v]);
			if (low[v] > dfn[u]){
				bridge++;
				e[i].cut = true;//标記此邊為橋 
				e[i^1].cut = true;
			}
		}
		else if(instack[v] && low[u] > dfn[v]){
			low[u] = dfn[v];
		}
	}
	if(low[u] == dfn[u]){//找到一個連通分量 
		ecc++;
		do{
			v = stack[--top];
			instack[v] = false;
			belong[v] = ecc;
		}while(v != u);
	}
}
int du[N];
void gao () {
	tarjan(1, 0);
	int ans = 0;
	for (int i = 1; i <= n; i++){
		for(int j = head[i]; j != -1; j = e[j].next){
			if (e[j].cut)
				du[belong[i]]++;
		}
	}
	for (int i = 1; i <= n; i++){
		if(du[i] == 1) ans++;
	}
	cout << (ans+1) / 2 << "\n";
}

void init () {
	memset(head, -1, sizeof(int) * (n+1));
	tot = 0;
	index = top = ecc = bridge = 0;
	memset(instack, false, sizeof(bool)*(n+1));
	memset(belong, 0, sizeof(int)*(n+1));
	memset(du, 0, sizeof(int)*(n+1));
}


int main () {
	while (~scanf("%d%d",&n, &m)) {
		init ();
		int u, v;
		for (int i = 0; i < m; i++) {
			scanf ("%d%d",&u, &v);
			addEdge(u, v);
			addEdge(v, u);
		}
		gao();
	}
	return 0;
}