Warm up HDU - 4612
DCC缩点后建立一棵树， 树中的所有边都是桥。 任意连接一条边使桥的数量最少。 那么就是要找出树的最长路径–树的直径。 ans = 桥的数量 - 树的直径
code：
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> using namespace std; const int N = 2e5 + 5, M = 1e6 + 5; struct node{ int u, v, next; } g[M * 2]; int dfn[N], low[N], index[N], depth[N], head[N], front[N], stack[N]; int cnt, opt, tot, cot; bool vis[N], vis_lca[N]; void add(int u, int v){ g[cnt].u = u; g[cnt].v = v; g[cnt].next = head[u]; head[u] = cnt++; return; } void init(int n){ cnt = opt = tot = cot = 0; for(int i = 1; i <= n; i++){ dfn[i] = low[i] = 0; vis[i] = false; index[i] = 0; head[i] = front[i] = -1; } return; } void targan(int u, int in_ridge){ dfn[u] = low[u] = ++opt; vis[u] = true; stack[cot++] = u; for(int i = head[u]; i != -1; i = g[i].next){ int v = g[i].v; if(!dfn[v]){ targan(v, i); low[u] = min(low[u], low[v]); } else if(vis[v] && i != (in_ridge ^ 1)) low[u] = min(low[u], dfn[v]); } if(dfn[u] == low[u]){ int res; tot++; do{ res = stack[--cot]; vis[res] = false; index[res] = tot; } while(u != res); } return; } int dfs_1(int u, int dep){ vis_lca[u] = true; depth[u] = dep; int sno = u; int sco; for(int i = front[u]; i != -1; i = g[i].next){ int v = g[i].v; if(!vis_lca[v]){ sco = dfs_1(v, dep + 1); if(depth[sno] < depth[sco]) sno = sco; } } return sno; } int dfs_2(int u, int dep){ vis_lca[u] = true; int sum = dep; for(int i = front[u]; i != -1; i = g[i].next){ int v = g[i].v; if(!vis_lca[v]) sum = max(sum, dfs_2(v, dep + 1)); } return sum; } int main(){ int n, m, x, y; while(scanf("%d%d", &n, &m), n && m){ init(n); for(int i = 1; i <= m; i++){ scanf("%d%d", &x, &y); add(x, y); add(y, x); } for(int i = 1; i <= n; i++) if(!dfn[i]) targan(i, -1); for(int i = 0; i < cnt; i++){ int u = g[i].u; int v = g[i].v; if(index[u] != index[v]){ g[i].u = index[u]; g[i].v = index[v]; g[i].next = front[index[u]]; front[index[u]] = i; } } for(int i = 1; i <= tot; i++) vis_lca[i] = false; int sno = dfs_1(1, 0); for(int i = 1; i <= tot; i++) vis_lca[i] = false; int sco = dfs_2(sno, 0); printf("%d\n", tot - 1 - sco); } }dalao的代码，从叶子节点开始，求树的直径和值得借鉴
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int N = 2e5 + 5, M = 4e6 + 6; struct E {int v, next;} e[M]; int n, m, u, v, len, ans, dh[N], h[N], dcc_cnt, id[N], num, dfn[N], low[N], d[N]; bool brid[M], vis[N]; void add(int h[], int u, int v) {e[++len].v = v; e[len].next = h[u]; h[u] = len;} void tarjan(int u, int in_edge) { dfn[u] = low[u] = ++num; for (int j = h[u]; j; j = e[j].next) { int v = e[j].v; if (!dfn[v]) { tarjan(v, j); low[u] = min(low[u], low[v]); if (dfn[u] < low[v]) brid[j] = brid[j ^ 1] = true; } else if ((j ^ 1) != in_edge) low[u] = min(low[u], dfn[v]); } } void dfs(int u) { id[u] = dcc_cnt; for (int j = h[u]; j; j = e[j].next) { int v = e[j].v; if (id[v] || brid[j]) continue; dfs(v); } } void dp(int u) { //倒着求树的直径代码 vis[u] = true; for (int j = dh[u]; j; j = e[j].next) { int v = e[j].v; if (vis[v]) continue; dp(v); ans = max(ans, d[u] + d[v] + 1); d[u] = max(d[u], d[v] + 1); } // } int main() { while (scanf("%d%d", &n, &m), n) { memset(h, 0, sizeof(h)); len = num = 1; memset(dh, 0, sizeof(dh)); memset(id, 0, sizeof(id)); memset(dfn, 0, sizeof(dfn)); memset(d, 0, sizeof(d)); memset(brid, false, sizeof(brid)); memset(vis, false, sizeof(vis)); for (int i = 1; i <= m; i++) { scanf("%d%d", &u, &v); add(h, u, v); add(h, v, u); } tarjan(1, 0); dcc_cnt = 0; //缩点 建树 for (int i = 1; i <= n; i++) { if (!id[i]) { dcc_cnt++; dfs(i); } } int tlen = len; for (int j = 2; j <= tlen; j += 2) { u = id[e[j].v], v = id[e[j ^ 1].v]; if (u == v) continue; add(dh, u, v); add(dh, v, u); } ans = 0; dp(1); //求出直径 printf("%d\n", dcc_cnt - 1 - ans); } return 0; }