题意：
n个旅游景点，r条路连接，无向图，现要维护每一条现有的道路，但维护当前road时需保证n个顶点仍然相互可达，问要保证上述条件，需新建几条road。即求一个无向图中需添加几条边，使之成为边双连通图。
思路：
通过tarjan求出边双连通分量，然后将每一个边双连通分量缩成一个点，将无向图最终会缩成一棵树，一棵所有边为原无向图中割边的树。
= =然后又要用到一个须知的结论：若要使得任意一棵树，在增加若干条边后，变成一个双连通图，那么至少增加的边数 =（这棵树中度数为1的结点数 + 1）/ 2。
在求构造树节点的度数貌似很麻烦。但不然，因为原图在tarjan之后所有相同low值的节点必定在同一个边双连通分量中，所以我们只需要枚举原图中直接连通的两点，如果不在同一个边双连通分量中，就将它们各自所在缩点的度数+1。注意是无向图，所有缩点的度数都会是真实度数的2倍，所以除2再判断就好。
//时隔仨月，做题终于做出这模板的bug了，tarjan之后所有相同low值的节点必定在同一个边双连通分量中这句话是对，但是low值不相同的也有可能是可能属于同一个边双连通分量的，代码已更。
代码：
#include <algorithm> #include <iostream> #include <string.h> #include <cstdio> #include <map> using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 1005; struct node { int u, v, next; }edge[maxn*2]; int no, head[maxn]; int dfn[maxn], low[maxn]; int top, S[maxn]; int bccno[maxn], bcc_cnt; int idx; map<int, int> mp; map<int, int>::iterator it; void init() { no = 0; idx = 0; bcc_cnt = 0; memset(head, -1, sizeof head); memset(dfn, 0, sizeof dfn); memset(bccno, 0, sizeof bccno); } inline void add(int u, int v) { edge[no].u = u; edge[no].v = v; edge[no].next = head[u]; head[u] = no++; } void tarjan(int u, int fa) { dfn[u] = low[u] = ++idx; S[++top] = u; for(int k = head[u]; k+1; k = edge[k].next) { int v = edge[k].v; if(!dfn[v]) { tarjan(v, u); low[u] = min(low[u], low[v]); } else if(v != fa) { low[u] = min(low[u], dfn[v]); } } if(dfn[u] == low[u]) { ++bcc_cnt; do { bccno[S[top]] = bcc_cnt; --top; } while(S[top+1] != u); } } int SuoDian() { mp.clear(); int ans = 0; for(int i = 0; i < no; ++i) { int u = edge[i].u, v = edge[i].v; if(bccno[u] != bccno[v]) ++mp[bccno[u]], ++mp[bccno[v]]; } for(it = mp.begin(); it != mp.end(); ++it) if(it->second/2 == 1) ++ans; return (ans+1)/2; } int main() { int n, r, u, v, maxx; while(~scanf("%d %d", &n, &r)) { init(); for(int i = 1; i <= r; ++i) { scanf("%d %d", &u, &v); add(u, v); add(v, u); } tarjan(1, -1); printf("%d\n", SuoDian()); } return 0; }
继续加油~
