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
#include <stdio.h>
#include <vector>
int n,m,d;

struct vertex{
//  int v;        // nazwa wierzcholka
  int deg ;     // stopien wierzcholka
  bool visited; // czy wierzcholek byl juz odwiedzany
  std::vector<int> edges;
  int color ;
  vertex() : deg(0), visited(false), edges(0), color(0) {}
  void addEdge(int vert){
    edges.push_back(vert);
    deg++;
  }
};

std::vector<vertex> V(200000+10);
int a,b;


int dfs(int v,int color){
  int s = 1;
  V[v].visited = true;
  V[v].color = color;
  for(int a : V[v].edges)
    if(!V[a].visited) s+=dfs(a,color);
  return s;
}

int main(){
  scanf("%d%d%d",&n,&m,&d);
  for(int i=0;i<m;++i){
    scanf("%d%d",&a,&b);
    V[a].addEdge(b);
    V[b].addEdge(a);
  }
  std::vector<int> stack(0); // stos miast nieodpowiednich
  // zainicjowac stos miastami o deg < d
  for(int i=1;i<=n;++i)
    if(V[i].deg < d) {
      stack.push_back(i);
      V[i].visited = true;
    }
  while (!stack.empty()){
    int w = stack.back();
    stack.pop_back();
    for(int a : V[w].edges) {
      V[a].deg--;
      if (V[a].deg < d && !V[a].visited) {
        stack.push_back(a);
        V[a].visited = true;
      }
    }
  }
  // kazdy nieodwiedzony wierzcholek ma stopien deg >=d do zbioru nieodwiedzonych
  // znalezc najwieksza spojna skladowa i ja wypisac
  int maxSize = 0;  // maksymalny rozmiar spojnej
  int color = 0;    // kolor reprezentujacy spojna najwieksza
  for(int i=1;i<=n;++i)
    if(!V[i].visited) {
      int s = dfs(i,i);
      if (s>maxSize) {maxSize = s; color = i;}
    }
  if(maxSize == 0) puts("NIE");
  else{
    printf("%d\n",maxSize);
    for(int i=1;i<=n;++i)
      if(V[i].color == color) printf("%d ",i);
    puts("");
  }
  return 0;
}