younik进入医院(并查集+STL)

题目：younik进入医院

分析： 我们首先来考虑如果那m队关系恰好可以构成一张联通图，那么我们如何来进行排列，我们先定义两个集合S和A,开始时集合S和A为空，第一步我们选则图中最小编号的点(为了满足题目要求的字典序最小)加入到集合S中。第二步从集合S中拿出最小的那个记为u，并将这个值加入到A集合中，之后遍历与u有关系且没在集合S中的点加入集合S中。 之后回到第一步直到集合S为空，这是集合A就为答案了。 理解只形成一张联通图的情况后，理解多张联通图与之类似，其中不高兴的人数就是形成联通图的张数。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int f[N],a[N],n,m,cnt=0,num=0;
vector<int> E[N];
set<int> S[N];
bool book[N];
int Find(int x){
	if(f[x]==x) return x;
	else return Find(f[x]);
}
void merge(int x,int y){
	int t1=Find(x),t2=Find(y);
	if(t1!=t2) f[t1]=t2;
}
void Init(){  //初始化
	cnt=0,num=0;
	for(int i=0;i<=n;i++) 
	f[i]=i,E[i].clear(),S[i].clear(),book[i]=false;
	
}
int main(){
	
	int t;
	scanf("%d",&t);
	while(t--){
		
		priority_queue<int,vector<int>,greater<int> > que;
		scanf("%d %d",&n,&m);
		Init();
		for(int i=1;i<=m;i++){
			int x,y;
			scanf("%d %d",&x,&y);
			merge(x,y);//判断两点是否在同一张连通图中，可以运用并查集
			E[x].push_back(y);
			E[y].push_back(x);
		}
		for(int i=1;i<=n;i++){
			if(Find(i)==i) cnt++; //统计连通图的数量
			S[Find(i)].insert(i);
		}
		for(int i=1;i<=n;i++){
			if(S[i].size()>0){
				que.push(*S[i].begin());//将每张联通图中编号最小的加入优先队列中(set自带从小到大排序)
				book[*S[i].begin()]=true;//别忘了标记
		
			}
		}
		while(!que.empty()){  
		
		
			int temp=que.top(); que.pop(); //que为上面分析的S集合
			a[num++]=temp;   //这里a数组就是上面分析的A集合
			for(int i=0;i<E[temp].size();i++){
				if(!book[E[temp][i]]){
		
					book[E[temp][i]]=true;
					que.push(E[temp][i]);
				}
				
			}
	
		}
		printf("%d\n",cnt);
		for(int i=0;i<num;i++){
			printf("%d ",a[i]);
		}
		printf("\n");
		
	} 
	
	
	
	
	
	
	return 0;
}