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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int ilosc_drog[200002];
int kandydaci[200002];
int odleglosci[200002];
vector < vector <int> >graf(200001);
vector < vector <int> >wyniki(200001);
queue <int> kolejka;
int main()
{

   int n,m,d,n1,n2;
   int licznik_miast=0;
   int v;
   scanf("%d%d%d",&n,&m,&d);
   for (int i=1;i<=m;i++)
   {
       scanf("%d%d",&n1,&n2);
       ilosc_drog[n1]++;ilosc_drog[n2]++;
       graf[n1].push_back(n2);
       graf[n2].push_back(n1);
   }
   for(int i=1;i<=n;i++)
   {
       if(ilosc_drog[i]>=d)
       {
           licznik_miast++;
           kandydaci[licznik_miast]=i;
       }
   }
   if (licznik_miast<2) {cout<<"NIE"; return 0;}
  /* cout<<"sasiedzi:"<<endl;
   for (int i=1;i<=n;i++)
   {
       for(int j=0;j<graf[i].size();j++)
        cout<<graf[i][j]<<" ";
       cout<<endl;
   }
   cout<<"ilosc drog "<<endl;
   for(int i=1;i<=n;i++)
     cout<<ilosc_drog[i]<<" ";
    cout<<endl<<"kandydaci"<<endl;
    for(int i=1;i<=licznik_miast;i++)
     cout<<kandydaci[i]<<" "; */
    ////////////////////////////////////////////////////////////////////////////////////
   bool koniec=false;
   int nowy_poczatek=kandydaci[1];
   int runda=0,maksi=0,runda_zw;
   while(!koniec)
   {
    odleglosci[nowy_poczatek]=1;
    for(int i=0;i<graf[nowy_poczatek].size();i++)
       if(ilosc_drog[graf[nowy_poczatek][i]]>=d) kolejka.push(graf[nowy_poczatek][i]);
    //cout<<endl;
    while (!kolejka.empty())
  {
    //cout<<" "<<kolejka.front();
    //kolejka.pop();
    v=kolejka.front();
    if(!odleglosci[v]) odleglosci[v]++;
    kolejka.pop();
    for(int i=0; i<graf[v].size();i++)
        if(ilosc_drog[graf[v][i]]>=d && odleglosci[graf[v][i]]==0)
             kolejka.push(graf[v][i]);
  }
  int licznik_ok=0,licznik_nieok=0;
    for(int i=1;i<=licznik_miast;i++)
        if(odleglosci[kandydaci[i]]>0) licznik_ok++;
            else {licznik_nieok++; nowy_poczatek=kandydaci[i];}
  //  cout<<licznik_ok<<"     nieok  "<<licznik_nieok<<endl;

    if(licznik_ok>=licznik_nieok && licznik_ok>=maksi)
    {
        cout<<licznik_ok<<endl;
       for(int i=1;i<=licznik_miast; i++)
        if(odleglosci[kandydaci[i]]>0) cout<<kandydaci[i]<<" ";
        koniec=true;
        return 0;
    } else
    {
       if(licznik_ok>maksi) {maksi=licznik_ok; runda_zw=runda;}
        koniec=false;
         for(int i=1;i<=licznik_miast; i++)
            if(odleglosci[kandydaci[i]]>0) wyniki[runda].push_back(kandydaci[i]);
        for(int i=1;i<=licznik_miast;i++)
            odleglosci[kandydaci[i]]=0;
    }
    }
    cout<<wyniki[runda_zw].size()<<endl;
    for(int i=0;i<wyniki[runda_zw].size();i++)
        cout<<wyniki[runda_zw][i]<<" ";
    return 0;
}