【BZOJ4296】[PA2015]Mistrzostwa
Description
给定一张n个点m条边的无向图，请找到一个点数最多的点集S，满足：
1.对于点集中任何一个点，它至少与d个点集中的点相邻。
2.仅保留点集中的点后，剩下的图连通。
Input
第一行包含三个正整数n,m,d(2<=n<=200000，1<=m<=200000，1<=d<n)，分别表示点数，边数以及度数限制。
接下来m行，每行包含两个正整数a,b(1<=a,b<=n，a不等于b)，表示a点和b点之间有一条边。
Output
若无解，输出NIE。
否则第一行输出一个正整数k，表示你找到的点数最多的点集S的点数。
第二行输出k个正整数，按升序依次输出点集中的点的编号，若有多组解，输出任意一组。
Sample Input
4 4 2
1 2
2 3
3 4
4 2
1 2
2 3
3 4
4 2
Sample Output
3
2 3 4
2 3 4
题解：这个应该叫调整法吧~
先将所有度数<d的点都扔进队列，然后删掉这些点与其他点之间的边，如果有其它点的度数也<d，那么将那个点也加入队列，不断BFS下去即可。有点类似于拓扑排序~
答案就是剩下的所有连通块中点数最多，且字典序最小的那个，并查集维护。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int maxn=200010;
int n,m,cnt,D,ans,mf;
int d[maxn],to[maxn<<1],next[maxn<<1],head[maxn],f[maxn],siz[maxn];
queue<int> q;
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
void add(int a,int b)
{
to[++cnt]=b,next[cnt]=head[a],head[a]=cnt;
}
int find(int x)
{
return (f[x]==x)?x:(f[x]=find(f[x]));
}
int main()
{
n=rd(),m=rd(),D=rd();
int i,j,a,b,u;
for(i=1;i<=m;i++) a=rd(),b=rd(),d[a]++,d[b]++,add(a,b),add(b,a);
for(i=1;i<=n;i++) if(d[i]<D) q.push(i);
while(!q.empty())
{
u=q.front(),q.pop();
for(i=head[u];i;i=next[i])
{
d[to[i]]--;
if(d[to[i]]==D-1) q.push(to[i]);
}
}
for(i=1;i<=n;i++) if(d[i]>=D) f[i]=i,siz[i]=1;
for(i=1;i<=n;i++) if(d[i]>=D) for(j=head[i];j;j=next[j]) if(d[to[j]]>=D&&find(i)!=find(to[j]))
{
a=min(f[i],f[to[j]]),b=max(f[i],f[to[j]]);
siz[a]+=siz[b],f[b]=a;
}
for(i=1;i<=n;i++) if(d[i]>=D&&find(i)==i&&siz[i]>ans) ans=siz[i],mf=i;
if(!ans)
{
printf("NIE
");
return 0;
}
printf("%d
",ans);
for(i=1;i<=n;i++) if(d[i]>=D&&find(i)==mf) printf("%d%c",i,!(--ans)?'
':' ');
return 0;
}