题目：
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个关系，求一个顺序（字典序最小）。第i个人进入时要是没有认识的人就会不开心，求怎么使不开心的人最少。输出这个序列。
分析：
首先，每个连通块里肯定至少有一个人不开心，取最优就是公共祖先不开心。（并查集）
用并查集时合并祖先时注意，让小的那个点当祖先。
然后，一个字典序最先的序列，用bfs+优先队列 爆搜 注意建图时要找一个超级连通点，让各个连通块连起来。（bfs）
好久没用vector存图了，还是喜欢前向星。
AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int f[N],vis[N],cnt[N],ans[N],k;
int tofind(int x){
if (f[x]!=x)
f[x]=tofind(f[x]);
return f[x];
}
void tojoin(int x,int y){
x=tofind(x);
y=tofind(y);
if(x<y)//合并时注意贪心一下
f[y]=x;
if(x>y)
f[x]=y;
}
vector <int> v[N];
void bfs(int st){//bfs就没什么好说的了
priority_queue<int, vector<int> ,greater<int> > q;
q.push(st);
while(!q.empty()){
int u=q.top();
q.pop();
if (vis[u])
continue;
vis[u]=1;
ans[k++]=u;
int l=v[u].size();
for (int i=0;i<l;i++){
int x=v[u][i];
if (vis[x])
continue;
q.push(x);
}
}
}
int main()
{
ios::sync_with_stdio(0);
int t,n,m,a,b;
cin>>t;
while(t--){
cin>>n>>m;
for (int i=0;i<=n;i++){
f[i]=i;
vis[i]=0;
v[i].clear();
}
for (int i=1;i<=m;i++){
cin>>a>>b;
tojoin(a,b);
v[a].push_back(b);//存图
v[b].push_back(a);
}
int sum=0;
for (int i=1;i<=n;i++){
if (tofind(i)==i){
cnt[sum++]=i;//sum统计连通块的个数，cnt 储存是那几条边，不过没这个必要
v[0].push_back(i);//0为超级连通点
}
}
k=0;
bfs(0);
cout<<sum<<"\n";
for (int i=1;i<k-1;i++)
cout<<ans[i]<<' ';
cout<<ans[k-1]<<"\n";
}
return 0;
}
不甘寂寞，自己用前向星实现了下 发现内存少了好多好多。
前向星大法好！ 但是第一次我因为没开2倍空间所以wa了一发。。
箭头指错了。↑
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int f[N],ans[N],k,head[N],cnt1;
bool vis[N];
int tofind(int x){
if (f[x]!=x)
f[x]=tofind(f[x]);
return f[x];
}
void tojoin(int x,int y){
x=tofind(x);
y=tofind(y);
if(x<y)
f[y]=x;
if(x>y)
f[x]=y;
}
struct edge{
int u,v,ne;
}ed[2*N]; //别忘啦 开2倍空间
void addedge(int u,int v){
ed[cnt1].u=u,ed[cnt1].v=v;
ed[cnt1].ne=head[u];
head[u]=cnt1++;
}
void bfs(int st){
priority_queue<int, vector<int> ,greater<int> > q;
q.push(st);
while(!q.empty()){
int u=q.top();
q.pop();
if (vis[u])
continue;
vis[u]=1;
ans[k++]=u;
for (int i=head[u];i!=-1;i=ed[i].ne){
int v=ed[i].v;
if (vis[v])
continue;
q.push(v);
}
}
}
int main()
{
ios::sync_with_stdio(0);
int t,n,m,a,b;
cin>>t;
while(t--){
cin>>n>>m;
for (int i=0;i<=n;i++){
f[i]=i;
vis[i]=0;
head[i]=-1;
cnt1=0;
}
for (int i=1;i<=m;i++){
cin>>a>>b;
tojoin(a,b);
addedge(a,b);
addedge(b,a);
}
int sum=0;
for (int i=1;i<=n;i++){
if (tofind(i)==i){
sum++;
addedge(0,i);
}
}
k=0;
bfs(0);
cout<<sum<<"\n";
for (int i=1;i<k-1;i++)
cout<<ans[i]<<' ';
cout<<ans[k-1]<<"\n";
}
return 0;
}
京公网安备 11010502036488号