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
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct Item
{
  unsigned int vert;
  unsigned int degree;
  Item(unsigned int v, unsigned int d):
    vert(v), degree(d) {};
};

struct Comp
{
  bool operator()(const Item& first, const Item& second)
  {
    return first.degree > second.degree;
  }
};

struct Data
{
  unsigned int actualSize;
  bool valid;
  unsigned int group;
  Data(unsigned int a): actualSize(a), valid(true), group(0) {};
};

void dfs(unsigned int root,
         vector< vector <int> >& vertex,
         vector<Data>& data,
         unsigned int group)
{
  data[root].group = group;
  for(unsigned int i=0; i<vertex[root].size(); ++i)
  {
    unsigned int neigh = vertex[root][i];
    if(data[neigh].valid and data[neigh].group==0)
    {
      dfs(neigh, vertex, data, group);
    }
  }
}

int main()
{
  unsigned int vertices;
  unsigned int edges;
  unsigned int minDegree;
  cin >> vertices;
  cin >> edges;
  cin >> minDegree;
  vector< vector <int> > vertex(vertices+1, vector<int>());
  vector< Data > data(vertices+1, Data(0));
  unsigned int first, second;
  for(unsigned int i=0; i<edges; ++i)
  {
    cin >> first;
    cin >> second;
    vertex[first].push_back(second);
    vertex[second].push_back(first);
  }

  priority_queue<Item, vector<Item>, Comp> que;
  for(unsigned int i=1; i<=vertices; ++i)
  {
    que.push(Item(i, vertex[i].size()));
    data[i].actualSize = vertex[i].size();
  }
  while(que.top().degree < minDegree)
  {
    Item toRemove = que.top();
    que.pop();
    if(data[toRemove.vert].valid)
    {
      for(unsigned int i=0; i<vertex[toRemove.vert].size(); ++i)
      {
        unsigned int neigh = vertex[toRemove.vert][i];
        if(data[neigh].valid)
        {
          data[neigh].actualSize--;
          que.push(Item(neigh, data[neigh].actualSize));
        }
      }
      data[toRemove.vert].valid = false;
    }
  }

  unsigned int group = 1;
  for(unsigned int i=1; i<=vertices; ++i)
  {
    if(data[i].valid and data[i].group==0)
    {
      dfs(i, vertex, data, group);
      ++group;
    }
  }

  vector<unsigned int> groups(group, 0);
  for(unsigned int i=1; i<=vertices; ++i)
  {
    if(data[i].valid)
      ++groups[data[i].group];
  }
  unsigned int maxGroup = 0;
  unsigned int count = 0;
  for(unsigned int i=1; i<group; ++i)
  {
    if(groups[i]>count)
    {
      count = groups[i];
      maxGroup = i;
    }
  }
  if(count==0)
    cout << "NIE";
  else
  {
    cout << count << endl;
    for(unsigned int i=1; i<=vertices; ++i)
    {
      if(data[i].group==maxGroup)
        cout << i << " ";
    }
  }
}