題意是給定一個無向圖,求增加一條邊後,橋的最少可能的條數。
先求出所有橋(即雙連通分量),然後縮點得到一顆樹。增加一條邊使得橋的數量最小,顯然是連接bcc樹上直徑的兩端了。
這個題hdu又會爆棧。。。開個掛才能過。。。
#pragma comment(linker,"/STACK:102400000,102400000") #include<iostream> #include<algorithm> #include<vector> #include<string> #include<queue> #include<stack> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<fstream> #include<sstream> #include<map> #include<set> #define FF(i, a, b) for(int i=a; i<b; i++) #define FD(i, a, b) for(int i=a; i>=b; i--) #define REP(i, n) for(int i=0; i<n; i++) #define CLR(a, b) memset(a, b, sizeof(a)) #define LL long long #define PB push_back #define debug puts("**debug**") using namespace std; const int maxn = 200001; int n, m, u, v; int pre[maxn], low[maxn], dfs_clock, bcc_cnt, bccno[maxn]; struct Edge { int to, flag; }; vector<int> G[maxn], g[maxn]; vector<Edge> edges; inline void init() { REP(i, n) G[i].clear(); edges.clear(); } void add(int u, int v) { Edge e; e.to = v, e.flag = 0; edges.PB(e); e.to = u; edges.PB(e); int nc = edges.size(); G[u].PB(nc-2); G[v].PB(nc-1); } int dfs(int u, int fa) { int lowu = pre[u] = ++dfs_clock; int nc = G[u].size(); REP(i, nc) { int v = edges[G[u][i]].to; if(!pre[v]) { int lowv = dfs(v, u); lowu = min(lowu, lowv); if(lowv > pre[u]) edges[G[u][i]].flag = 1, edges[G[u][i]^1].flag = 1; } else if(pre[v] < pre[u] && v != fa) lowu = min(lowu, pre[v]); } return low[u] = lowu; } void dfs1(int u) { bccno[u] = bcc_cnt; int nc = G[u].size(); REP(i, nc) { int v = edges[G[u][i]].to; if(!bccno[v] && edges[G[u][i]].flag != 1) dfs1(v); } } void find_bcc() { CLR(pre, 0); CLR(bccno, 0); dfs_clock = bcc_cnt = 0; REP(i, n) if(!pre[i]) dfs(i, -1); REP(i, n) if(!bccno[i]) bcc_cnt++, dfs1(i); } int mm, end; void find(int u, int fa, int d) { int nc = g[u].size(); if(nc == 1) { if(d > mm) { mm = d; end = u; } } REP(i, nc) { int v = g[u][i]; if(v != fa) find(v, u, d+1); } } int main() { while(scanf("%d%d", &n, &m), n+m) { init(); REP(i, m) { scanf("%d%d", &u, &v); u--; v--; add(u, v); } find_bcc(); if(bcc_cnt == 1) { puts("0"); continue; } REP(i, n+1) g[i].clear(); REP(u, n) { int nc = G[u].size(); REP(i, nc) { int v = edges[G[u][i]].to; if(bccno[u] != bccno[v]) g[bccno[u]].PB(bccno[v]); } } mm = 0; find(1, -1, 0); find(end, -1, 0); printf("%d\n", bcc_cnt - mm - 1); } return 0; }