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
#include <cstdlib>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct City
{
   City() : group(0) {}
   int group;
   int count;
   vector<int> neight;
};

City Cities[200001];
queue<int> ToProcess;


int main(int argc, char *argv[])
{
   int n,m,d;
   cin>>n>>m>>d;
   for(int i = 0; i < m; i++)
   {
      int a,b;
      cin>>a>>b;
      
      Cities[a].neight.push_back(b);
      Cities[b].neight.push_back(a);
   }
   
   for(int i = 1; i <= n; i++)
   {
      Cities[i].count = Cities[i].neight.size();
      if(Cities[i].count < d)
      {
         Cities[i].group = -1;
         ToProcess.push(i);
      }
   }
   
   //part one remove cities with neightbours less than d
   while(ToProcess.empty() == false)
   {
      int a = ToProcess.front();
      for(vector<int>::iterator it = Cities[a].neight.begin(); it != Cities[a].neight.end(); ++it)
      {
         int b = *it;
         if(Cities[b].group != 0) //it is or was on ToProcess queue
            continue;
         
         Cities[b].count--;
         if(Cities[b].count < d)
         {
            Cities[b].group = -1;
            ToProcess.push(b);
         }
      }
      ToProcess.pop();
   }
   
   //all cities have minimum d roads
   //lets split this to group
   int maxGroup = 0;
   int maxGroupSize = 0;
   int CurrentGroup = 1;
   
   for(int s = 1; s <= n; s++)
   {
      if(Cities[s].group != 0)
         continue;
      
      Cities[s].group = CurrentGroup;
      ToProcess.push(s);
      
      int CurrentGroupSize = 0;
      while(ToProcess.empty() == false)
      {
         CurrentGroupSize++;
         int a = ToProcess.front();
         for(vector<int>::iterator it = Cities[a].neight.begin(); it != Cities[a].neight.end(); ++it)
         {
            int b = *it;
            if(Cities[b].group != 0) //it is or was on ToProcess queue
               continue;
            
            Cities[b].group = CurrentGroup;
            ToProcess.push(b);
         }
         ToProcess.pop();
      }
      
      if(CurrentGroupSize > maxGroupSize)
      {
         maxGroupSize = CurrentGroupSize;
         maxGroup = CurrentGroup;
      }
      
      CurrentGroup++;
   }
   
   if(maxGroupSize == 0)
   {
      cout<<"NIE";
      return 0;
   }
   
   cout<<maxGroupSize<<endl;
   
   vector<int> Final;
   for(int i = 1; i <= n; i++)
   {
      if(Cities[i].group == maxGroup)
         Final.push_back(i);
   }
   
   for(vector<int>::iterator it = Final.begin(); it != Final.end(); ++it)
   {
      cout<<*it<<" ";
   }
}