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
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct City{
   vector<int> neighbours;
   int degree;
   bool ok=true;
   bool visited=false;
};

vector<City> cities;

vector<int> BFS(int start){
   cities[start].visited = true;
   vector<int> skladowa;
   skladowa.push_back(start);
   vector<int> stack;
   stack.push_back(start);
   while(!stack.empty()){
      int f = stack.back();
      stack.pop_back();
      for(int n : cities[f].neighbours){
         if(!cities[n].visited && cities[n].ok){
            cities[n].visited = true;
            stack.push_back(n);
            skladowa.push_back(n);
         }
      }
   }
   return skladowa;
}

int main(){
   int n,m,d;
   scanf("%d%d%d",&n,&m,&d);
   n+=1;
   cities.resize(n);
   for(int i=0;i<m;++i){
      int a,b;
      scanf("%d%d",&a,&b);
      cities[a].neighbours.push_back(b);
      cities[b].neighbours.push_back(a);
   }
   for(int i=0;i<n;++i){
      cities[i].degree = cities[i].neighbours.size();
   }
   deque<int> citiesToRemove;
   for(int i=0;i<n;++i){
      if(cities[i].degree<d){
         citiesToRemove.push_back(i);
         cities[i].ok=false;
      }
   }
   while(!citiesToRemove.empty()){
      int current = citiesToRemove.front();
      citiesToRemove.pop_front();
      for(int ne : cities[current].neighbours){
         cities[ne].degree-=1;
         if(cities[ne].degree<d && cities[ne].ok){//if it's ok it wasn't queued for removal yet so do it
            cities[ne].ok = false;
            citiesToRemove.push_back(ne);
         }
      }
   }
   //we now have a graph having only edges with enough vertices
   //find its biggest spójną składową
   vector<int> biggest;
   for(int i=0;i<n;++i){
      if(cities[i].ok && !cities[i].visited){
         vector<int> spojna = BFS(i);
         if(spojna.size()>biggest.size()) biggest=spojna;
      }
   }
   if(biggest.size()>0){
      sort(biggest.begin(),biggest.end());
      printf("%ld\n",biggest.size());
      for(int i=0;i<biggest.size();++i) printf("%d ",biggest[i]);
      puts("");
   }else{
      puts("NIE");
   }
}