Degree of Spanning Tree 生成树 + 思维
题目大意：
给你一张 (n) 个节点 (m) 条边的无向图，你可以删去一些节点使得这张图变成一棵树，要求每一个节点的度数小于等于 (frac{n}{2})
题解：
要一步一步的分析
-
首先分析如何把一张图变成一棵树，并查集即可。
-
对于一棵树，它最多只有一个节点的度数要 (>frac{n}{2}) ，定义 (d(i)) 表示节点 (i) 的度数，对于任意两个节点 ((u,v))，(d(u)+d(v)<=n) ，这个很容易理解，你可以假设 (u) 和它所连的点形成一个连通块，那么 (v) 和它所连的点中最多有一个点连到了 (u) 所在的哪个连通块，如果有两个及以上就会形成一个环，假设 (u) 所在的连通块的数量是 (x)，那么减去 (u) ，所以度数是 (x-1)，(v) 所在的连通块数量最大是 (n-x)，所以度数是 (n-x-1) ，如果 (u) 和 (v) 直接相连，那么会加上2的度数，所以就是 (n)
因为 (d(u)+d(v)<=n) 所以最多有一个节点的度数 (>frac{n}{2})
-
所以先变成任意的一个生成树，找到度数 (>frac{n}{2}) 的这个节点 (rt)，接下来遍历不在生成树里面的边，如果存在一条边，它的加入会形成一个包含 (rt) 的环，那么就加入这条边，删去一条和 (rt) 相连的边。
-
注意在这个过程中，可能会出现另外一个点 (id) ，使得 (d[id]>frac{n}{2}) ，但是从上述证明中可以发现的是的是 (id) 一定和 (rt) 一定相邻，否则 (d[id]+d[rt]<=n-2) ，所以在加边的过程中注意一下不要出现这种情况即可。
难点：
- 每次加一条边，如何保证这条边的加入会形成一个包含 (rt) 的环。
- 因为我们只要研究一个根节点，而且这个根节点是已经确定下来的。
- 那么我们找到这个根节点的所有儿子节点 (v)，以这些节点作为根节点来遍历他们的子节点，然后更新他们的子节点的父节点为 (v) 即可。
- 之后的加边，我只要判断两个节点是不是属于不同的子节点，如果是，那么不让他称为一个新的 (id) 即可，如果不是，那么就要忽略这条边的处理
这个题目写的时候，还是要注意细节，最后如果一条边被删去了，那么要对这个边的并查集数组重新赋值，这个赋值是有方向的！！！
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
struct node{
int u,v,id;
node(int u=0,int v=0,int id=0):u(u),v(v),id(id){}
}e[maxn];
vector<node>G[maxn];
bool vis[maxn];
int f[maxn],in[maxn],fa[maxn],dep[maxn];
void add(int u,int v,int id){
G[u].push_back(node(u,v,id));
G[v].push_back(node(v,u,id));
}
int findx(int x){
return f[x]==x?x:f[x] = findx(f[x]);
}
void unite(int x,int y){
x = findx(x),y = findx(y);
if(x==y) return ;
f[x] = y;
}
bool same(int x,int y){
return findx(x)==findx(y);
}
void dfs(int u,int pre,int t){
f[u] = t,dep[u] = dep[pre]+1;
for(int i=0;i<G[u].size();i++){
int v = G[u][i].v;
if(v==pre) continue;
dfs(v,u,t);
}
}
void print(int m){
printf("Yes
");
for(int i=1;i<=m;i++){
if(vis[i]) printf("%d %d
",e[i].u,e[i].v);
}
}
int main(){
int T;
scanf("%d",&T);
while (T--){
int n,m,rt = 0;
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++) f[i] = i,G[i].clear(),in[i] = 0;
for(int i=0;i<=m;i++) vis[i] = false;
for(int i=1;i<=m;i++) {
int u,v;
scanf("%d%d",&u,&v);
e[i] = node(u,v,i);
if(!same(u,v)) unite(u,v),vis[i] = true,in[u]++,in[v]++,add(u,v,i);
if(in[u]>in[rt]) rt = u;
if(in[v]>in[rt]) rt = v;
}
if(n==3){
printf("No
");
continue;
}
dep[rt] = 0,f[rt] = rt;
for(int i=0;i<G[rt].size();i++){
int v = G[rt][i].v;
fa[v] = G[rt][i].id;
dfs(v,rt,v);
}
for(int i=1;i<=m;i++){
if(in[rt]<=n/2) break;
int u = e[i].u,v = e[i].v;
int fu = findx(u),fv = findx(v);
if(fu==fv||u==rt||v==rt) continue;
if(dep[u]<dep[v]) swap(u,v),swap(fu,fv);
if(dep[v]==1&&in[u]>in[v]) swap(u,v),swap(fu,fv);
++in[u],++in[v],--in[rt],--in[fv];
vis[e[i].id] = true,vis[fa[fv]] = false;
f[fv] = fu;//!!!!
}
if(in[rt]>n/2) printf("No
");
else print(m);
}
return 0;
}