本文主要是介绍codeforces723F st-Spanning Tree(连通性t)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给出一个n个顶点m条边的无向图，并给出两个点s，t和对应的度数，要求将图转变为一颗生成树，并且s，t的度数要满足要求。
要点：
生成树也就是把原图的边减少至n-1条边，并且所有的点都连通。这题的思路是将st除去的图进行连通操作，然后此时这些连通块可以分为二种：
1.只和st其中一个相连
2.和st两个都相连
我们需要先将第一种连通块的先连在st上，因为它是必须要连的，否则没有地方可以连。接着连接第二种连通块与st连接，这一步中，只要一个连通块与st均连接，其他的与st其中任意一个连接。这里一开始我觉得很难写，后来发现只要第一个连通块与st均连接，st就已经连接，之后再进行连接操作，连通块也不会同时连接到st两个上。最后考虑一下如果到最后还不能使st相连，只能连接原本存在的st这条边。原则上只要第二种连通块存在就不连接原本的st边，因为第二种连通块本身起码要要连接st中一个，就算两个都连，对度数消耗也就是2，而如果连接st原边，度数消耗就是3。
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 400000 + 5;
int n, m;
pair<int, int> edge[maxn];
int used[maxn], fa[maxn],dd[maxn];
int cs[maxn], ct[maxn];int find(int x)//并查集
{return fa[x] == x ? x : (fa[x] = find(fa[x]));
}int main()
{int i, j;int s, t, ds, dt;int st = 0, cnt = 0;scanf("%d%d", &n, &m);for (i = 1; i <= m; i++)scanf("%d%d", &edge[i].first, &edge[i].second);scanf("%d%d%d%d", &s, &t, &ds, &dt);for (i = 1; i <= m; i++)if (edge[i] == make_pair(s, t) || edge[i] == make_pair(t, s))st = i; //s与t这条边是否存在for (i = 1; i <= n; i++)fa[i] = i;for (i = 1; i <= m; i++)//先将除st以外的点连通起来{int u = edge[i].first, v = edge[i].second;if (u == s || v == s || u == t || v == t)continue;dd[i] = 1;if (find(u) == find(v))continue;fa[find(u)] = find(v);cnt++; used[i] = 1;}for (i = 1; i <= m; i++)//这步是判断每个连通块是否与st连接{if (dd[i]) continue;if (st == i) continue;int u = edge[i].first, v = edge[i].second;if (u == s) cs[find(v)] = 1;if (u == t) ct[find(v)] = 1;if (v == s) cs[find(u)] = 1;if (v == t) ct[find(u)] = 1;}for (i = 1; i <= m; i++)//这一步就是将只有与st其中一个点连通的连通块和st连通{if (dd[i]) continue;if (st == i) continue;int u = edge[i].first, v = edge[i].second;if (!ds && (u == s || v == s)) continue;if (!dt && (u == t || v == t)) continue;if (u != s&&u != t && (cs[find(u)]&& ct[find(u)])) continue;if (v != s&&v != t && (cs[find(v)]&& ct[find(v)])) continue;if (find(u) == find(v))continue;if (u == s || v == s) ds--;if (u == t || v == t) dt--;fa[find(u)] = find(v);cnt++;used[i] = 1;}for (i = 1; i <= m; i++)//这一步就是处理与st两个都连通的连通块{ //注意只要第一个连通块均与st相连，st就已经连通，后面的连通块只能加到st其中一个上if (dd[i]) continue;if (st == i) continue;int u = edge[i].first, v = edge[i].second;if (!ds && (u == s || v == s)) continue;if (!dt && (u == t || v == t)) continue;if (find(u) == find(v))continue;if (u == s || v == s) ds--;if (u == t || v == t) dt--;fa[find(u)] = find(v);cnt++;used[i] = 1;}if (find(s) != find(t) && ds&&dt)//如果到最后st都不连通，说明没有和st都连接的连通块，只能连通st这条边{used[st] = 1;cnt++;}if (cnt < n - 1){printf("No\n");return 0;}else{printf("Yes\n");for (i = 1; i <= m; i++)if (used[i])printf("%d %d\n", edge[i].first, edge[i].second);}return 0;
}这篇关于codeforces723F st-Spanning Tree(连通性t)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
