题目：Redundant Paths
总结 ：这道题先给一个无向连通图，问加最少的边使这个图成为双连通图。 可以先用tarjan求出桥，并且给桥做出标记。然后再用dfs给每一个点标记一个新的编号，这个地方需要利用br数组，此时的br数组为1 的是保存的是桥的起点和终点。然后统计这个新图的度为1的点 答案 = （新图度为1的点+1）/2
#include <stdio.h> #include <string.h> #include <map> #include <algorithm> using namespace std; typedef pair<int,int>P; const int N = 11005; const int mod = 1000000007; struct st{ int x,y; }a[N<<2]; int dfn[N],low[N],head[N],ans[N]; bool br[N]; int colour[N];//对新的图进行染色 int n,cnt,len,m,dcc; struct str{ int v; int next; }e[N<<5]; void init(){ memset(ans,0,sizeof ans); memset(br,0,sizeof br); memset(colour,0,sizeof colour); memset(head,0,sizeof head); memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); cnt = 1; len = 0; dcc = 0; } void add(int x,int y){ e[++cnt].v = y; e[cnt].next = head[x]; head[x] = cnt; } void tarjan(int u,int in){ dfn[u] = low[u] = ++len; for(int i = head[u];i;i = e[i].next){ int v = e[i].v; int x = u,y = v; if(!dfn[v]){ tarjan(v,i); low[u] = min(low[u],low[v]); if(dfn[u] < low[v]){ br[i] = br[i^1] = 1; } }else if(i != (in^1)){ low[u] = min(low[u],dfn[v]); } } } void dfs(int u){ colour[u] = dcc; for(int i = head[u];i;i = e[i].next){ int v = e[i].v; //对桥不进行访问，对进行遍历的点不进行访问 if(colour[v] || br[i]) continue; dfs(v); } } void solve(){ init(); for(int i = 0;i < m;i++){ int x,y; scanf("%d%d",&x,&y); a[i].x = x;a[i].y = y; add(x,y); add(y,x); } //求桥 for(int i = 1;i <= n;i++){ if(!dfn[i]){ tarjan(i,0); } } //对新图进行染色 for(int i = 1;i <= n;i++){ if(!colour[i]){ ++dcc; dfs(i); } } for(int i = 0;i < m;i++){ if(colour[a[i].x] == colour[a[i].y]) continue; else { ans[colour[a[i].x]]++; ans[colour[a[i].y]]++; } } int sum = 0; for(int i = 1;i <= n;i++){ if(ans[i] == 1) sum++; } printf("%d\n",(sum+1)/2); } int main(){ while(~scanf("%d%d",&n,&m)){ solve(); } return 0; }