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
129
130
131
132
133
134
// Potyczki Algorytmiczne 2015
// runda 2
// MIStrzostwa
// Tomasz Pastusiak

#include <iostream>
#include <algorithm>
#include <functional>
#include <stack>
#include <set>
#include <vector>

using namespace std;

#define MAX_M_N 200001

int connectionLevel[MAX_M_N]; // 1 .. n
bool badCityNoticed[MAX_M_N]; // 1 .. n
stack<int> badCities; // this could be a stack
vector<int> g[MAX_M_N];

int groupNumber[MAX_M_N];
int groupSizes[MAX_M_N];

int main(){
    ios_base::sync_with_stdio(false);

    int n,m,d,a,b;
    cin >> n >> m >> d;

    for(int i=1 ;i<=n; ++i){
        connectionLevel[i] = 0;
        badCityNoticed[i] = false;
        groupNumber[i] = -1;
        groupSizes[i] = 0;
    }

    for(int i=0; i<m; ++i){
        cin >> a >> b;
		++connectionLevel[a];
		++connectionLevel[b];
        g[a].push_back(b);
        g[b].push_back(a);
    }

    /*for(int i=1; i<=n ; ++i){
        cout << "City " << i << " lev: " << connectionLevel[i] << " noticed: " << badCityNoticed[i] << " good: " << (connectionLevel[i] >= d ? 'Y' : 'N') << endl;
    }*/

    // now we know which cities are good, just check connectionLevel[city] >= d

    for(int i=1 ;i<=n; ++i){
        if(connectionLevel[i] < d){
            badCities.push(i);
            badCityNoticed[i] = true;
        }
    }

    /*cout << "---------" << endl;

    for(int i=1; i<=n ; ++i){
        cout << "City " << i << " lev: " << connectionLevel[i] << " noticed: " << badCityNoticed[i] << " good: " << (connectionLevel[i] >= d ? 'Y' : 'N') << endl;
    }*/

    while(!badCities.empty()){
        int badass = badCities.top();
        badCities.pop();
        for(int i=0; i<g[badass].size(); ++i){
            int otherCity = g[badass][i];
            --connectionLevel[ otherCity ];
            if(connectionLevel[ otherCity ] < d && badCityNoticed[otherCity] == false){
                badCities.push(otherCity);
                badCityNoticed[otherCity] = true;
            }
        } // for each friend of bad city
    }

    /*cout << "---------" << endl;

    for(int i=1; i<=n ; ++i){
        cout << "City " << i << " lev: " << connectionLevel[i] << " noticed: " << badCityNoticed[i] << " good: " << (connectionLevel[i] >= d ? 'Y' : 'N') << endl;
    }*/

    // now we have to do DFS (BFS) to count sizes of groups

	stack<int> searchStack;

	for(int i=1 ;i<=n; ++i){
		if(groupNumber[i] == -1){
			groupNumber[i] = i;
			if(badCityNoticed[i]) continue;
			searchStack.push(i);
			
			while(!searchStack.empty()){
				int v = searchStack.top();
				searchStack.pop();
				
				for(int j=0; j<g[v].size(); ++j){
					int otherCity = g[v][j];
					if(badCityNoticed[otherCity] == false && groupNumber[otherCity] == -1){
						groupNumber[otherCity] = groupNumber[v];
						searchStack.push(otherCity);
					} // if friend is also good and unvisited, add it to group
				} // for each friend of good city
			}
			
		} // if doesn't belong to any group
    }

	for(int i=1 ;i<=n; ++i){
		++groupSizes[ groupNumber[i] ];
    }
    
    int biggestGroup = 1;
    
    for(int i=1 ;i<=n; ++i){
		if(groupSizes[i] > groupSizes[biggestGroup]) biggestGroup = i;
    }
    
    if( badCityNoticed[biggestGroup] ){
		cout << "NIE" << endl;
	}
	else{
		cout << groupSizes[biggestGroup] << endl;
		
		for(int i=1 ;i<=n; ++i){
			if(groupNumber[i] == biggestGroup) cout << i << ' ';
		}
		
		cout << endl;
	}
    
    return 0;
}