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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>

using namespace std;

int main() {
	uint i,j;
	uint n, m, d;
	int a,b;

	scanf("%d %d %d", &n, &m, &d);

	vector<vector<int> > v(n+2);

	for (i = 0; i < m; ++i) {
		scanf("%d %d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}


	vector<bool> S(n+2, 0);
	queue<int> Q;
	vector<bool> waiting_in_Q(n+2, false);
	for (i = 1; i <= n; ++i) {
		waiting_in_Q[i] = false;
		S[i] = false;

		// mark all potential S-cities
		if (v[i].size() >= d) {
			S[i] = true;
			Q.push(i);
			waiting_in_Q[i] = true;
		}
	}

	int ii = 0;
	int p, cnt, q;
	while (Q.size() > 0) {
		p = Q.front();
		Q.pop();

		ii++;
		//printf("%d ", p);

		waiting_in_Q[p] = false;

		// count neighboring S-cities
		cnt = 0;
		for (i = 0; i < v[p].size(); ++i) {
			if (S[v[p][i]]) cnt++;
		}

		// if too few neighboring S-cities remove from S, and add neighbors to check-list
		if (cnt < d) {
			S[p] = false;
			for (i = 0; i < v[p].size(); ++i) {
				q = v[p][i];
				if (S[q] && !waiting_in_Q[q]) {
					Q.push(q);
					waiting_in_Q[q];
				}
			}
		}
	}

	// find components
	vector<int> comp(n+2, 0);
	vector<bool> odw(n+2, false);
//
//	for (i = 1; i <= n; ++i) {
//		printf("[%d] S=%d comp=%d\n", i, S[i]?1:0, comp[i]);
//	}

	int largest_comp = 0;
	int best_comp = -1;
	int ind = 1;
	for (i = 1; i <= n; ++i) {
		//printf("try [%d] S=%d comp=%d\n", i, S[i], odw[i]);
		if (S[i] && !odw[i]) {
			//printf("go!\n");

			// find component connected with i-th city
			Q.push(i);
			odw[i] = true;
			int curr_size = 0;

			while (Q.size() > 0) {
				p = Q.front();
				Q.pop();

				//printf("visit %d\n", p);

				comp[p] = ind;
				curr_size++;

				for (j = 0; j < v[p].size(); ++j) {
					q = v[p][j];
					if (S[q] && !odw[q]) {
						Q.push(q);
						odw[q] = true;
					}
				}
			}

			if (curr_size > largest_comp) {
				best_comp = ind;
				largest_comp = curr_size;
			}

			ind++;
		}
	}

	if (best_comp == -1) {
		printf("NIE");
		return 0;
	}

	printf("%d\n", largest_comp);
	for (i = 1; i <= n; ++i) if (comp[i] == best_comp) printf("%d ", i);
	printf("\n");

	return 0;
}