聚会(party.c/cpp/pas)
2.1 题目描述
你要精心策划一场聚会。
现在有 n 个人，一共有 m 个认识关系，认识的人一定是相互认识的。由于这次聚会十
分重要，你希望被邀请的每个人都直接或间接认识，不仅如此，为了避免尴尬，你还希望每
个被邀请的人都直接认识另外至少 d 个被邀请的人。作为策划者，你希望使得被邀请的人
最多。注意同一对关系最多只会出现一次，且不会出现自环。
你需要输出被邀请的人数，并且将被邀请的人的编号从小到大输出。为了避免你的重度
选择恐惧症发作，当存在多个答案时，你需要使得被邀请的人的编号越小越好。
2.2 输入格式
第一行为三个整数 n，m，d，分别表示人数、认识关系数以及题中给出的限制 d。
接下来 m 行 ，每行两个数 a 和 b，表示 a、b 相互认识。
2.3 输出格式
第一行一个整数，表示被邀请的人数 k。保证有解，即 k>0。
第二行 k 个整数，从小到大输出你邀请的人的编号。
2.4 样例输入
4 4 2
1 2
2 3
3 4
4 2
2.5 样例输出
NOIP 模拟试题 #5
5
3
2 3 4
2.6 数据范围与约定
对于 20％的数据，n<=18，m<=50
对于 100％的数据，2<=n<=200000, 1<=m<=200000 , 1<=d<n
#include<iostream> #include<cstdio> #include<queue> #include<algorithm> #include<cstring> using namespace std; int n,m,d; int in[200009]; int h[200009],nex[200009*2],to[200009*2],cnt; int f[200009],sum[200009]; bool vis[200009]; int A[200009],B[200009]; int find(int x) { if(x!=f[x]) f[x]=find(f[x]); return f[x]; } int main() { scanf("%d%d%d",&n,&m,&d); int a,b; for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); A[i]=a,B[i]=b; in[a]++,in[b]++; to[++cnt]=a,nex[cnt]=h[b],h[b]=cnt; to[++cnt]=b,nex[cnt]=h[a],h[a]=cnt; } for(int i=1;i<=n;i++) sum[i]=1,f[i]=i; queue<int>q; for(int i=1;i<=n;i++) if(in[i]<d) q.push(i),vis[i]=1; while(!q.empty()) { int i=q.front();q.pop(); if(in[i]<d ) { for(int j=h[i];j;j=nex[j]) { in[to[j]]--; if((!vis[to[j]])&&in[to[j]]<d)//这里写成了，竟然编译过了，竟然没找出错来 q.push(to[j]),vis[to[j]]=1; } } } int maxn=0,maxw=9999999; for(int i=1;i<=m;i++) { if(in[A[i]]>=d && in[B[i]]>=d) { int f1=find(A[i]),f2=find(B[i]); if(f1==f2) continue; f[f1]=f2;sum[f2]+=sum[f1]; if(sum[f2]>maxn) maxn=sum[f2],maxw=f2; } } printf("%d ",maxn); for(int i=1;i<=n;i++) if(find(i)==maxw) printf("%d ",i); return 0; }
输入
18 19 2
9 11
1 15
13 15
3 1
7 16
11 13
17 6
3 13
5 1
7 2
4 15
7 6
11 3
5 10
9 16
6 5
7 1
7 3
17 16
输出
11
1 3 5 6 7 9 11 13 15 16 17