题目：Warm up 总结：答案就是用桥的数量减去缩点之后树的直径，找了半天也没找到我哪里错了，最后还是对照着别人的代码，一点一点看的。 学一下树形DP https://blog.nowcoder.net/n/ecee5d8c275842ba8df777de342d038a
#include <bits/stdc++.h> using namespace std; typedef pair<int,int>P; const int N = 2e5+5; const int M = 2e6+5; vector<int>G[N]; struct st{ int x,y; }a[N<<9]; int dfn[N],low[N],head[N],d[N],vis[N]; bool br[M]; int colour[N];//对新的图进行染色 int n,cnt,num,m,dcc,ans,sum; struct str{ int v; int next; }e[M<<5]; 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] = ++num; for(int i = head[u];i;i = e[i].next){ int v = e[i].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; sum++; } }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); } } //树形dp，求树的哪两个点的之间的距离最长，求出距离 void dp(int u){ vis[u] = 1; for(int i = 0;i < G[u].size();i++){ int v = G[u][i]; if(vis[v]) continue; dp(v); //max{u到叶节点的最大距离+子节点到叶节点的最大距离+u到v的距离} ans = max(ans,d[u]+d[v]+1); //max{子节点到叶节点的最大距离+当前点到子节点的距离} d[u] = max(d[u],d[v]+1); } } void init(){ for(int i = 0;i < N;i++){ G[i].clear(); } memset(vis,0,sizeof vis); memset(d,0,sizeof d); memset(colour,0,sizeof colour); memset(br,0,sizeof br); memset(head,0,sizeof head); memset(low,0,sizeof low); memset(dfn,0,sizeof dfn); cnt = 1; dcc = 0; num = 0; ans = 0; sum = 0; } int main(){ while(scanf("%d%d",&n,&m)&&(n+m)){ init(); for(int i = 0;i < m;i++){ scanf("%d%d",&a[i].x,&a[i].y); add(a[i].x,a[i].y); add(a[i].y,a[i].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++){ int u = colour[a[i].x]; int v = colour[a[i].y]; if(u != v){ G[u].push_back(v); G[v].push_back(u); } } dp(1); printf("%d\n",sum-ans); } return 0; }