題干：

The 44th World Finals of the International Collegiate Programming Contest (ICPC 2020) will be held in Moscow, Russia. To celebrate this annual event for the best competitive programmers around the world, it is decided to host a welcome party for all??participants of the World Finals, numbered from??to??for convenience.

The party will be held in a large hall. For security reasons, all participants must present their badge to the staff and pass a security check in order to be admitted into the hall. Due to the lack of equipment to perform the security check, it is decided to open only one entrance to the hall, and therefore only one person can enter the hall at a time.

Some participants are friends with each other. There are??pairs of mutual friendship relations. Needless to say, parties are more fun with friends. When a participant enters the hall, if he or she finds that none of his or her friends is in the hall, then that participant will be unhappy, even if his or her friends will be in the hall later. So, one big problem for the organizer is the order according to which participants enter the hall, as this will determine the number of unhappy participants. You are asked to find an order that minimizes the number of unhappy participants. Because participants with smaller numbers are more important (for example the ICPC director may get the number 1), if there are multiple such orders, you need to find the lexicographically smallest one, so that important participants enter the hall first.

Please note that if participant??and??are friends, and if participant??and??are friends, it's NOT necessary that participant??and??are friends.

Input

There are multiple test cases. The first line of the input contains a positive integer?, indicating the number of cases. For each test case:

The first line contains two integers??and??(), the number of participants and the number of friendship relations.

The following??lines each contains two integers??and??(), indicating that the?-th and the?-th participant are friends. Each friendship pair is only described once in the input.

It is guaranteed that neither the sum of??nor the sum of??of all cases will exceed?.

Output

For each case, print a single integer on the first line, indicating the minimum number of unhappy participants. On the second line, print a permutation of??to?separated by a space, indicating the lexicographically smallest ordering of participants entering the hall that achieves this minimum number.

Consider two orderings??and?, we say??is lexicographically smaller than?, if there exists an integer??(), such that??holds for all?, and?.

Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!

Sample Input

2 4 3 1 2 1 3 1 4 4 2 1 2 3 4

Sample Output

1 1 2 3 4 2 1 2 3 4

題目大意：有n個人m個關系，每一對關系代表這兩人認識，關系不具有傳遞性，現在你要安排這n個人進入一個舞會，如果第i個人進入了舞會大廳但是發現沒有一個認識的人，那就會不高興。問你怎么安排順序這n個人進入舞會大廳，使得不開心的人數最少。如果有多種方案，輸出字典序最小的方案。

解題報告：

? 首先每一個連通塊肯定有一個人是不開心的，并且可以做到只有一個人是不開心的，所以有多少連通塊，就有多少人不開心。對于字典序，只需要搞個優先隊列遍歷就可以了。然后因為有多個連通塊，肯定不能一個塊一個塊的遍歷，所以需要弄一個超級源點連到所有的起點上，然后再遍歷，注意連到每個聯通塊的起點，這個起點需要是整個塊的最小值，這樣肯定使得結果最優。而讓塊的祖先節點是最小值，這一點可以用并查集稍作修改實現。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e6 + 5; int f[MAX],n,m; int getf(int v) {return f[v] == v ? v : f[v] = getf(f[v]); } void merge(int u,int v) {int t1 = getf(u);int t2 = getf(v);if(t1>t2) f[t1] = t2;else f[t2]=t1; } int ans[MAX],tot,vis[MAX]; vector<int> vv[MAX]; void bfs(int st) {priority_queue<int,vector<int>,greater<int> > pq;pq.push(st);while(!pq.empty()) {int cur = pq.top();pq.pop();if(vis[cur] == 1) continue;vis[cur] = 1;ans[++tot] = cur;int up = vv[cur].size();for(int i = 0; i<up; i++) {int v = vv[cur][i];if(vis[v]) continue;pq.push(v);}} } int main() {int t;cin>>t;while(t--) {tot=0;scanf("%d%d",&n,&m);for(int i = 0; i<=n; i++) f[i] = i,vv[i].clear(),vis[i]=0;for(int u,v,i = 1; i<=m; i++) {scanf("%d%d",&u,&v);vv[u].pb(v);vv[v].pb(u);merge(u,v);}int ans1 = 0;for(int i = 1; i<=n; i++) {if(f[i] == i) vv[0].pb(i),ans1++;}bfs(0);printf("%d\n",ans1);for(int i = 2; i<=tot; i++) {printf("%d%c",ans[i],i==tot ? '\n': ' ');}}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【2019浙江省赛 - J】Welcome Party（并查集，bfs，优先队列，建图）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。