老年人需要大一点的字体。
紫书习题11-17 NEERC2011
给定一棵树，然后让你加入尽量少的边，使得整张图双连通。
这个uva1670好像数据错了，非常难受，怎么搞都过不去，然后网上现有的题解都是各种奇技淫巧，非常奇怪。
所以自己想了想然后还是自己写了一个，虽然wa了无数次，最后还是在Uvalive5920获得了一个AC，也算是不枉花费的时间了。
先上代码：
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mem(a) memset(a,0,sizeof(a)) typedef long long ll; typedef pair<int,int> pii; const int mn=1e5+5; int n,root; int f[mn]; vector<int> g[mn],son[mn],leaf; vector<pii> ans; void dfs(int x,int fa){ f[x]=fa; for(auto i:g[x]){ if (i==fa) continue; dfs(i,x); } if (g[x].size()==1){ leaf.pb(x); if (leaf.size()==3){ int u=leaf[1]; ans.pb(pii(leaf[0],x)); leaf.clear(); leaf.pb(u); } } } int main() { while(~scanf("%d",&n)){ ans.clear(); for(int i=1;i<=n;i++) g[i].clear(),son[i].clear(),f[i]=0; for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); g[u].pb(v); g[v].pb(u); } if (n==2){ puts("1\n1 2"); } for(int i=1;i<=n;i++){ if (g[i].size()>1) { root=i; break; } } dfs(root,0); if (leaf.size()==2) { int u=leaf.back(); int v=*leaf.begin(); leaf.clear(); ans.pb(pii(u,v)); } for(int i:leaf) ans.pb(pii(root,i)); leaf.clear(); //answer printf("%d\n",ans.size()); for(auto i:ans) printf("%d %d\n",i.first,i.second); } return 0; }我们先随便选一个度数大于2的点作为树根，然后从该树根延展出去。
显然，直接延展出去的每一条边都是一座桥。
为了去除连接每棵子树的根到更上层的桥，每棵子树应该预留下一个点（连上去），所以每棵子树都要留一个点或者两个点（三个点的时候就可以连接两个点了），这样一步步上去，搞搞好就ac辣。
