题目链接:()( https://vjudge.net/problem/ZOJ-4109 )
题面复制不过来.
题意: n 个人, 编号为 1~n,m 个朋友关系 (a 和 b 是朋友, a 和 c 是朋友不代表 b 和 c 是朋友), 将 n 个人按照顺序排好, 如果一个人前面没有他的朋友那么不满意度加一, 让你给出一个排序使得不满意度最小化, 有相同结果的排序输出字典序最小的那个.
有关系存在, 考虑画图. 画完图后发现不满意度的最小值即是图的连通分量的个数, 因为每当选定一个连通分量的的人进入序列, 与他连接的人就可以都顺着连接加入序列, 从而不会增加不满意度. 求连通分量个数可用并查集实现.
要求输出字典序最小的, 想到了用优先队列实现的 bfs, 优先选择队列中编号最小的点.
因为用 memset 导致超时好几次, 初始化时最好用多少初始化多少.
代码:
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <queue>
- typedef long long ll;
- using namespace std;
- const int N=1e6+5;
- struct cmp {
- bool operator()(int a,int b) {
- return a>b;
- }
- };
- priority_queue <int,vector <int>,cmp> Q;
- int E[N<<1],fir[N],nex[N<<1],tot;
- int per[N];
- bool vis[N];
- bool book[N];
- int n,m,cnt;
- void init() {
- for(int i=1;i<=n;i++) {
- per[i]=i;fir[i]=-1;vis[i]=false;book[i]=false;
- }
- cnt=tot=0;
- }
- void connect(int from,int to) {
- E[tot]=to;
- nex[tot]=fir[from];
- fir[from]=tot++;
- E[tot]=from;
- nex[tot]=fir[to];
- fir[to]=tot++;
- }
- int root(int x) {
- int tempa,tempb;
- tempa=x;
- while(x!=per[x]) x=per[x];
- while(per[tempa]!=x) {
- tempb=per[tempa];
- per[tempa]=x;
- tempa=tempb;
- }
- return x;
- }
- void merge(int x,int y) {
- int t1=root(x);
- int t2=root(y);
- if(t1!=t2) {
- per[t1]=t2;cnt++;
- }
- }
- void solve() {
- int cnt=0;
- while(!Q.empty()) {
- int q=Q.top();Q.pop();
- if(vis[q]) continue;
- vis[q]=true;
- cnt++;
- printf("%d",q);
- if(cnt!=n) printf(" ");
- for(int i=fir[q];i!=-1;i=nex[i]) {
- int to=E[i];
- if(!vis[to]) Q.push(to);
- }
- }
- printf("\n");
- }
- int main() {
- int t;
- scanf("%d",&t);
- while(t--) {
- scanf("%d%d",&n,&m);
- init();
- for(int i=1;i<=m;i++) {
- int x,y;
- scanf("%d%d",&x,&y);
- connect(x,y);
- merge(x,y);
- }
- printf("%d\n",n-cnt);
- for(int i=1;i<=n;i++) {
- if(!book[root(i)]) {
- book[root(i)]=true;
- Q.push(i);
- }
- }
- solve();
- }
- return 0;
- }
来源: https://www.cnblogs.com/liaxiaoquan/p/12423815.html