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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <stdio.h>
#include <algorithm>
#include <vector>

using std::vector;

struct town {
	int id;
	vector<int> connection;
	int dead_connections;

	town()
	{
		dead_connections = 0;
	}

	bool operator<(const struct town &one) const
	{
		return id < one.id;
	}

};

struct zone {
	vector<struct town> town;
};

/* increase the dead_connections counter for the town id and kill neighbours if nessesary */
void kill_and_conquer(int id, int d, vector<struct town> &town, bool *used, vector<int> &valid)
{
	town[id].dead_connections++;
	if (town[id].connection.size() - town[id].dead_connections < d) {
		used[id] = true;
		valid.erase(std::remove(valid.begin(), valid.end(), id), valid.end());
		for (int i = 0; i < town[id].connection.size(); i++) {
			int id2 = town[id].connection[i];
			if (!used[id2])
				kill_and_conquer(id2, d, town, used, valid);
		}

	}
}

int main()
{

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

	vector<struct town> town;
	town.resize(n);

	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		/* get the index */
		a--;
		b--;

		town[a].connection.push_back(b);
		town[a].id = a;

		town[b].connection.push_back(a);
		town[b].id = b;
	}

	/* init to false */
	bool *used = new bool[n]();

	/* create a vector of valid ids */
	vector<int> valid;
	for (int i = 0; i < n; i++) {
		valid.push_back(i);
	}

	/* remove small towns */
	for (int i = 0; i < town.size(); i++) {
		if (town[i].connection.size() < d) {
			/* current town has already been processed (dead_conn) */
			if (used[i]) {
				continue;
			}

			used[i] = true;
			/* increase the ammount of dead connections */
			for (int j = 0; j < town[i].connection.size(); j++) {
				int id = town[i].connection[j];
				if (!used[id])
					kill_and_conquer(id, d, town, used, valid);

			}

			/* find and remove the id from the valid list */
			valid.erase(std::remove(valid.begin(), valid.end(), i), valid.end());
		}
	}

	vector<struct zone> zone;
	int best_zone = 0;
	int best_value = 0;

	/* create zones while there are items in the valid list */
	for (int i = 0; valid.size(); i++) {
		zone.resize(i+1);
		zone[i].town.reserve(1);

		/* pop the first unused town into the current zone, set it as used and delete it */
		zone[i].town.push_back(town[valid[0]]);
		used[valid[0]] = true;
		valid.erase(valid.begin());

		/* max denotes the ammount of towns in the current zone */
		int max = 1;
		for (int j = 0; j < max; j++) {
			/* dump all connections from a town from the zone into the zone */
			for (int k = 0; k < zone[i].town[j].connection.size(); k++) {
				int id = zone[i].town[j].connection[k];
				if (!used[id]) {
					zone[i].town.push_back(town[id]);
					/* find and remove the id */
					valid.erase(std::remove(valid.begin(), valid.end(), id), valid.end());
					used[id] = true;
					max++;
				}
			}
		}

		if (zone[i].town.size() > best_value) {
			best_zone = i;
			best_value = zone[i].town.size();
		}
	}

	delete[] used;

	if (best_value == 0) {
		printf("NIE\n");
		return 0;
	}

	printf("%d\n", best_value);
	sort(zone[best_zone].town.begin(), zone[best_zone].town.end());

	for (int i = 0; i < zone[best_zone].town.size(); i++) {
		printf("%d ", zone[best_zone].town[i].id + 1);
	}
	putchar('\n');

	return 0;

}