BZOJ 4296 PA2015 Mistrzostwa

题目大意：给定一张无向图，求一个点集最大的诱导子图使得：
1.每个点的度数都$\geq d$
2.诱导子图连通

将所有度数不足$d$的点都加入队列
每次取出队头，将队头相邻的点度数减掉1，如果减掉后度数变成了$d-1$那么将这个点加入队列
输出剩余点的最大连通块即可

#include 
#include 
#include 
#include 
#define M 200200
using namespace std;struct abcd{int to,next;
}table[M<<1];
int head[M],tot;int n,m,d;
int degree[M];
bool deleted[M];
int v[M];
int q[M],r,h;
int size,ans,ans_point;
int stack[M],top;void Add(int x,int y)
{table[++tot].to=y;table[tot].next=head[x];head[x]=tot;
}void DFS(int x)
{int i;if(v[x]||deleted[x])return ;v[x]=1;++size;for(i=head[x];i;i=table[i].next)DFS(table[i].to);
}void Output_Ans(int x)
{int i;if(v[x]==2||deleted[x])return ;v[x]=2;stack[++top]=x;for(i=head[x];i;i=table[i].next)Output_Ans(table[i].to);
}int main()
{int i,x,y;cin>>n>>m>>d;for(i=1;i<=m;i++){scanf("%d%d",&x,&y);Add(x,y);Add(y,x);degree[x]++;degree[y]++;}for(i=1;i<=n;i++)if(degree[i]q[++r]=i;while(r!=h){int x=q[++h];deleted[x]=true;for(i=head[x];i;i=table[i].next)if(degree[table[i].to]--==d)q[++r]=table[i].to;}if(r==n){puts("NIE");return 0;}for(i=1;i<=n;i++)if(!deleted[i]&&!v[i]){size=0;DFS(i);if(size>ans)ans=size,ans_point=i;}cout<sort(stack+1,stack+top+1);for(i=1;i<=top;i++)printf("%d%c",stack[i],i==top?'\n':' ');return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！