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
#include<cstdio>
#include<algorithm>
int LiczbaMiast,LiczbaDrog,D;
struct Droga{int a;int b;};
Droga dr[200010*2];
int di[200010], dl[200010], dl2[200010];
int k[200010];
int g[200010];
int grmax;
bool f1(Droga a, Droga b){return (a.a<b.a);}
void usunmiastojesliD(int i){
  if(dl2[i]<D && dl2[i]>0){k[i]=-1; 
for(int j=0;j<dl[i];j++){dl2[dr[di[i]+j].b]--;}  
for(int j=0;j<dl[i];j++)usunmiastojesliD(dr[di[i]+j].b);
}}
void dodaj(int i, int gr){
if (k[i]==0){k[i]=gr;
for(int j=0;j<dl[i];j++){dodaj(dr[di[i]+j].b,gr);}}
}

main(){
scanf("%d%d%d",&LiczbaMiast,&LiczbaDrog,&D);
for(int i=0,a,b;i<LiczbaDrog;i++)scanf("%d%d",&a,&b),dr[i].a=a,dr[i].b=b,dr[i+LiczbaDrog].a=b,dr[i+LiczbaDrog].b=a;
LiczbaDrog*=2;
std::sort(dr,dr+LiczbaDrog,f1);
for(int i=0,a,b;i<LiczbaDrog;i++){if(!dl[dr[i].a])di[dr[i].a]=i; dl[dr[i].a]++; dl2[dr[i].a]++;} 
for(int i=1;i<=LiczbaMiast;i++){if(dl2[i]) usunmiastojesliD(i);}
grmax=1;
for(int i=1;i<=LiczbaMiast;i++){if (k[i]==0) dodaj(i,grmax++); }
int ogmax=0,ogk=0;
for(int i=1;i<=LiczbaMiast;i++)if(k[i]>0){int t=++g[k[i]];if (t>ogmax)ogmax=t,ogk=k[i];}
if (ogmax>1){printf("%d\n",ogmax);for(int i=1;i<=LiczbaMiast;i++)if(k[i]==ogk)printf("%d ",i);printf("\n");}else printf("NIE\n");
}