4296: [PA2015]Mistrzostwa
Time Limit: 10 Sec Memory Limit: 256 MBSec Special Judge
Submit: 60 Solved: 26
[Submit][Status][Discuss]
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
HINT
请不要提交，尚无SPJ
Source
现将所有点中度数小于d的店删除。。然后删除连向其他点的边。。直到没有度数小于d的点。。
然后对于剩下的求最大联通块。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2000100;
struct data{int x,y,next;} e[N<<1];
int head[N],del[N],vis[N],q[N],s[N],ans1[N],ans,n,m,d,cnt,sum,In[N],h,t,x,y;
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
void Insert(int x,int y){
e[++cnt].x = x;e[cnt].y = y;
e[cnt].next = head[x];head[x] = cnt;
}
int Bfs(){
h = t = 0;
for (int i=1;i<=n;i++)
if (In[i]<d) q[++t] = i,del[i] = 1;
while (h<t){
int now = q[++h];
for (int i=head[now];i;i=e[i].next){
In[e[i].y]--;
if (In[e[i].y]<d && !del[e[i].y]) q[++t] = e[i].y,del[e[i].y] = 1;
}
}
return t!=n;
}
void dfs(int x){
vis[x] = 1;s[++sum] = x;
for (int i=head[x];i;i=e[i].next)
if (!vis[e[i].y] && !del[e[i].y]) dfs(e[i].y);
}
int main(){
n = read();m = read();d = read();
for (int i=1;i<=m;i++){
x = read();y = read();
Insert(x,y);Insert(y,x);
In[x]++;In[y]++;
}
if (!Bfs()) return printf("NIE"),0;
for (int i=1;i<=n;i++)
if (!vis[i] && !del[i]){
sum = 0;dfs(i);
if (ans<sum){ans = sum;for (int i=1;i<=sum;i++) ans1[i] = s[i];}
}
printf("%d\n",ans);
sort(ans1+1,ans1+1+ans);
for (int i=1;i<ans;i++) printf("%d ",ans1[i]);printf("%d\n",ans1[ans]);
}
评论 (0)
