题目地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=6011

题意

有n个人m个关系，每一对关系代表这两人认识，关系不具有传递性，现在你要安排这n个人进入一个舞会，如果第i个人进入了舞会大厅但是发现没有一个认识的人，那就会不高兴。问你怎么安排顺序这n个人进入舞会大厅，使得不开心的人数最少。如果有多种方案，输出字典序最小的方案。

 

解题思路

  首先每一个连通块肯定有一个人是不开心的，并且可以做到只有一个人是不开心的，所以有多少连通块，就有多少人不开心。对于字典序，只需要搞个优先队列遍历就可以了。然后因为有多个连通块，肯定不能一个块一个块的遍历，所以需要弄一个超级源点连到所有的起点上，然后再遍历，注意连到每个联通块的起点，这个起点需要是整个块的最小值，这样肯定使得结果最优。而让块的祖先节点是最小值，这一点可以用并查集稍作修改实现。
（以上文字来源：https://blog.csdn.net/qq_41289920/article/details/89605547 ）

注意：可能会出现 （1，2） （2，1） 这种情况，那么1的朋友（vector存）里面会有两个2，优先队列bfs遍历的时候要避免重复遍历2的朋友们，否则在报wa之前会内存超限！！（终于找到原因了(;´༎ຶД༎ຶ`)）

 

ac代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define maxn 1000005
using namespace std;
int f[maxn],n,m,x,y;
int ans[maxn],num,vis[maxn];
vector<int> fr[maxn];
int findf(int x) {
    return f[x] == x ? x : f[x] = findf(f[x]);
}
void bfs(int x) {
    priority_queue<int,vector<int>,greater<int> > q;
    q.push(x);
    while(!q.empty()) {
        int k = q.top();q.pop();
        if(vis[k] == 1) continue;
        vis[k] = 1;
        ans[num++] = k;
        int up = fr[k].size();
        for(int i = 0; i<up; i++) {
            int v = fr[k][i];
            if(!vis[v])
               q.push(v);
        }
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--) {
        num=0;
        scanf("%d%d",&n,&m);
        for(int i = 0; i<=n; i++) f[i] = i,fr[i].clear(),vis[i]=0;
        for(int i = 1; i<=m; i++) {
            scanf("%d%d",&x,&y);
            fr[x].push_back(y);fr[y].push_back(x);
            int fx = findf(x);
            int fy = findf(y);
            if(fx>fy) f[fx] = fy;
            else f[fy]=fx;
        }
        int ans1 = 0;
        for(int i = 1; i<=n; i++) {
            if(f[i] == i) fr[0].push_back(i),ans1++;
        }
        bfs(0);
        printf("%d\n",ans1);
        for(int i = 1; i<num; i++) {
            if(i!=1) printf(" ");
            printf("%d",ans[i]);
        }
        printf("\n");
    }
    return 0 ;
}