Welcome Party ZOJ - 4109

本文主要是介绍Welcome Party ZOJ - 4109，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4109

不开心总人数即连通块数 每个块出一个编号最小的人 贪心考虑 与其相识的人可以下批入场 优先队列维护拓扑即可

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=1e6+10;struct node
{int val;bool friend operator < (node n1,node n2){return n1.val>n2.val;}
};vector <int> edge[maxn];
priority_queue <node> que;
int f[maxn],minn[maxn],ans[maxn],book[maxn];
int n,m,num,tot;void init()
{int i;for(i=1;i<=n;i++){edge[i].clear();f[i]=i,minn[i]=i,book[i]=0;}
}int getf(int p)
{if(f[p]==p) return p;else return f[p]=getf(f[p]);
}void unite(int u,int v)
{int fu,fv;fu=getf(u),fv=getf(v);if(fu!=fv){f[fv]=fu;minn[fu]=min(minn[fu],minn[fv]);}
}void toposort()
{node cur,tmp;int i,u,v;while(!que.empty()) que.pop();num=0,tot=0;for(i=1;i<=n;i++){if(f[i]==i){tmp.val=minn[i];que.push(tmp);book[minn[i]]=1;tot++;}}while(!que.empty()){cur=que.top();que.pop();u=cur.val;ans[++num]=u;for(i=0;i<edge[u].size();i++){v=edge[u][i];if(!book[v]){tmp.val=v;que.push(tmp);book[v]=1;}}}
}int main()
{int t,i,u,v;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);init();while(m--){scanf("%d%d",&u,&v);edge[u].pb(v),edge[v].pb(u);unite(u,v);}toposort();printf("%d\n",tot);for(i=1;i<=n;i++){printf("%d",ans[i]);if(i<n) printf(" ");else printf("\n");}}return 0;
}

 

这篇关于Welcome Party ZOJ - 4109的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---