#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cstdlib> #include<cmath> #include<vector> #include<map> #include<set> #include<queue> #include<bitset> using namespace std; #define inf 1000000005 typedef long long ll; typedef double db; void gn(int &x){ int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-'); if(c=='-')sg=-1,x=0;else x=c-'0'; while((c=getchar())>='0'&&c<='9')x=x*10+c-'0'; x*=sg; } void gn(ll &x){ int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-'); if(c=='-')sg=-1,x=0;else x=c-'0'; while((c=getchar())>='0'&&c<='9')x=x*10+c-'0'; x*=sg; } const int mo=1000000007; int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;} int gcd(int a,int b){return b?gcd(b,a%b):a;} int n,m,d; struct edge{ int v,next; }e[555555];int g[222222];int etot=0; void ae(int u,int v){ e[etot].v=v;e[etot].next=g[u];g[u]=etot++; } int deg[222222]={0}; int qu[222222];int p=0,q=0; int vis[222222]; int fa[222222],sz[222222]; int gf(int x){return x==fa[x]?x:fa[x]=gf(fa[x]);} void un(int x,int y){ x=gf(x),y=gf(y); if(x!=y)sz[y]+=sz[x],fa[x]=y; } int main() { memset(g,-1,sizeof(g)); scanf("%d%d%d",&n,&m,&d); while(m--){ int u,v; gn(u);gn(v); ae(u,v); ae(v,u); deg[v]++; deg[u]++; } for (int i=1;i<=n;i++)if(deg[i]<d)vis[qu[q++]=i]=1; while(p!=q){ int u=qu[p++]; for (int i=g[u];~i;i=e[i].next)if(!vis[e[i].v]) if(--deg[e[i].v]<d)vis[qu[q++]=e[i].v]=1; } for (int i=1;i<=n;i++)fa[i]=i,sz[i]=1; for (int u=1;u<=n;u++)if(!vis[u]) for (int i=g[u];~i;i=e[i].next)if(!vis[e[i].v])un(u,e[i].v); int ma=0,an; for (int i=1;i<=n;i++)if(!vis[i] && fa[i]==i)ma=max(ma,sz[i]); for (int i=1;i<=n;i++)if(!vis[i] && fa[i]==i && sz[i]==ma)an=i; if(ma==0)printf("NIE\n"); else{ printf("%d\n",ma); for (int i=1;i<=n;i++)if(gf(i)==an)printf("%d ",i); printf("\n"); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | #include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cstdlib> #include<cmath> #include<vector> #include<map> #include<set> #include<queue> #include<bitset> using namespace std; #define inf 1000000005 typedef long long ll; typedef double db; void gn(int &x){ int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-'); if(c=='-')sg=-1,x=0;else x=c-'0'; while((c=getchar())>='0'&&c<='9')x=x*10+c-'0'; x*=sg; } void gn(ll &x){ int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-'); if(c=='-')sg=-1,x=0;else x=c-'0'; while((c=getchar())>='0'&&c<='9')x=x*10+c-'0'; x*=sg; } const int mo=1000000007; int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;} int gcd(int a,int b){return b?gcd(b,a%b):a;} int n,m,d; struct edge{ int v,next; }e[555555];int g[222222];int etot=0; void ae(int u,int v){ e[etot].v=v;e[etot].next=g[u];g[u]=etot++; } int deg[222222]={0}; int qu[222222];int p=0,q=0; int vis[222222]; int fa[222222],sz[222222]; int gf(int x){return x==fa[x]?x:fa[x]=gf(fa[x]);} void un(int x,int y){ x=gf(x),y=gf(y); if(x!=y)sz[y]+=sz[x],fa[x]=y; } int main() { memset(g,-1,sizeof(g)); scanf("%d%d%d",&n,&m,&d); while(m--){ int u,v; gn(u);gn(v); ae(u,v); ae(v,u); deg[v]++; deg[u]++; } for (int i=1;i<=n;i++)if(deg[i]<d)vis[qu[q++]=i]=1; while(p!=q){ int u=qu[p++]; for (int i=g[u];~i;i=e[i].next)if(!vis[e[i].v]) if(--deg[e[i].v]<d)vis[qu[q++]=e[i].v]=1; } for (int i=1;i<=n;i++)fa[i]=i,sz[i]=1; for (int u=1;u<=n;u++)if(!vis[u]) for (int i=g[u];~i;i=e[i].next)if(!vis[e[i].v])un(u,e[i].v); int ma=0,an; for (int i=1;i<=n;i++)if(!vis[i] && fa[i]==i)ma=max(ma,sz[i]); for (int i=1;i<=n;i++)if(!vis[i] && fa[i]==i && sz[i]==ma)an=i; if(ma==0)printf("NIE\n"); else{ printf("%d\n",ma); for (int i=1;i<=n;i++)if(gf(i)==an)printf("%d ",i); printf("\n"); } return 0; } |