F2
这道题还是非常有意思的,题意很简单,就是给定一个图,和图上的双向边,要求1号节点的度(连接边的条数)等于K,求这棵树的生成树。
我们首先要解决,如何让1号节点的度时为k的呢???而且求的是生成树,意思是不是所有边都会选择。那么我们如何选择才能保证1号节点有K个度呢???这里就要考虑联通分量的问题了,我们刨除1号点,那么联通分量的个数,就是我们让图联通的最小个数,因此我们需要用并查集,把点分在不同的联通块内部。
再考虑我们每个联通块,至少需要1条连接1号点的边。不够K再添加连接1号点的边。
然后考虑由于是生成树,我们可以枚举每个联通块连接1的点,DFS找出生成树边,记录即可。
DFS+并查集版本:
#include<iostream> #include<string.h> #include<stdio.h> #include<algorithm> #include<vector> #define pii pair<int,int> #define mp make_pair using namespace std; const int maxx = 2e5+7; int fa[maxx]; vector<int>G[maxx]; vector<int>p; vector<pii>ans; struct node {int u,v; } a[maxx]; int vis[maxx]; int v[maxx]; int Find(int x) {return fa[x]==x?x:(fa[x]=Find(fa[x])); } void dfs(int x) {int nex;for (int i=0; i<G[x].size(); i++){nex=G[x][i];if (nex==1)continue;if (v[nex]==0){v[nex]=1;ans.push_back(mp(x,nex));dfs(nex);}} } int main() {int n,m,k;while(~scanf("%d%d%d",&n,&m,&k)){ans.clear();memset(vis,0,sizeof(vis));memset(v,0,sizeof(v));for (int i=1; i<=n; i++){fa[i]=i;}for (int i=1; i<=m; i++){scanf("%d%d",&a[i].u,&a[i].v);G[a[i].u].push_back(a[i].v);G[a[i].v].push_back(a[i].u);if (a[i].u!=1 && a[i].v!=1){int fx=Find(a[i].u),fy=Find(a[i].v);fa[fx]=fy;}}int cnt=0;for (int i=1; i<=m; i++){if (a[i].u==1 || a[i].v==1){int fx=Find(a[i].u),fy=Find(a[i].v);if (fx!=fy){vis[i]=2;if (a[i].u==1){p.push_back(a[i].v);}else{p.push_back(a[i].u);}v[a[i].u]=2;v[a[i].v]=2;ans.push_back(mp(a[i].u,a[i].v));cnt++;fa[fx]=fy;}else{vis[i]=1;}}}if (cnt>k){printf("NO\n");continue;}k-=cnt;for (int i=1; i<=m; i++){if (k==0)break;if(vis[i]==1){k--;ans.push_back(mp(a[i].u,a[i].v));if (a[i].u==1){p.push_back(a[i].v);}else {p.push_back(a[i].u);}v[a[i].u]=2;v[a[i].v]=2;vis[i]=2;}}if (k!=0){printf("NO\n");continue;}v[1]=1;printf("YES\n");for (int i=0; i<p.size(); i++){dfs(p[i]);}for (int i=0; i<ans.size(); i++){printf("%d %d\n",ans[i].first,ans[i].second);}}return 0; }
当然有大佬提出了更牛逼的做法,仍然是用并查集,单独处理连接1的边,然后枚举每条边,当这个点的不是指向1的,并且边的两点却不在一个连通分量里面,那么这条边是必选的。
并查集版本:
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<vector> using namespace std; const int maxx = 2e5+7; struct node {int u,v; } a[maxx]; int fa[maxx]; int vis[maxx]; int Find(int x) {return fa[x]==x?x:(fa[x]=Find(fa[x])); }; int add(int x,int y) {int fx=Find(x),fy=Find(y);if(fx!=fy)fa[fx]=fy; } int main() {int n,m,d,k;int u,v;while(~scanf("%d%d%d",&n,&m,&k)){memset(vis,0,sizeof(vis));for (int i=1; i<=n; i++){fa[i]=i;}for (int i=1; i<=m; i++){scanf("%d%d",&a[i].u,&a[i].v);if (a[i].u!=1 && a[i].v!=1){int fx=Find(a[i].u),fy=Find(a[i].v);if (fx!=Find(fy)){fa[fx]=fy;}}}int cnt=0;for (int i=1; i<=m; i++){if (a[i].u==1 || a[i].v==1){int fx=Find(a[i].u),fy=Find(a[i].v);if(fx!=fy){vis[i]=2;//必选fa[fx]=fy;cnt++;}else{vis[i]=1;//备选 }}}if (cnt>k){printf("NO\n");continue;}k-=cnt;for (int i=1; i<=m; i++) //选择剩下的和1相连的数目 {if (k==0)break;if (vis[i]==1){vis[i]=2;//cout<<i<<endl;k--;int fx=Find(a[i].u),fy=Find(a[i].v);fa[fx]=fy;}}if (k!=0){printf("NO\n");continue;}for (int i=1; i<=n; i++) //再次初始化 {fa[i]=i;}for (int i=1;i<=m;i++){if (vis[i]==2){int fx=Find(a[i].u),fy=Find(a[i].v);fa[fx]=fy;}}for (int i=1; i<=m; i++){if (a[i].u!=a[i].v && a[i].u!=1 && a[i].v!=1){int fx=Find(a[i].u),fy=Find(a[i].v);if (fx!=fy){fa[fx]=fy;vis[i]=2;}}}printf("YES\n");for (int i=1;i<=m;i++){if(vis[i]==2) printf("%d %d\n",a[i].u,a[i].v);}}return 0; }
转载于:.html
更多推荐
F2
发布评论