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
#include<iostream>
#include<list>
#include<stack>

using namespace std;

int main() {
	int ile_miast, ile_drog, d;
	int miasto1, miasto2;
	bool byla_zmiana = false;	

	cin >> ile_miast;
	cin >> ile_drog;
	cin >> d;
	list<int> rozklad_drog[ile_miast + 1];
	int ile_drog_tab[ile_miast + 1];
	for (int i = 1; i <= ile_miast; i++)
		ile_drog_tab[i] = 0;

	for (int i = 1; i <= ile_drog; i++) {
		cin >> miasto1;
		cin >> miasto2;
		ile_drog_tab[miasto1]++;
		ile_drog_tab[miasto2]++;
		rozklad_drog[miasto1].push_front(miasto2);
		rozklad_drog[miasto2].push_front(miasto1);
	}
//	for (int i = 1; i <= ile_drog; i++)
//		for (auto it = rozklad_drog[i].begin(); it != rozklad_drog[i].end(); it++)
//			cout << "miasto" << i << " = " << *it << endl;
	do {
		byla_zmiana = false;
		for (int i = 1; i <= ile_miast; i++) {
			if (ile_drog_tab[i] < d && ile_drog_tab[i] > -1) {
				byla_zmiana = true;
				ile_drog_tab[i] = -1;
				for (auto it = rozklad_drog[i].begin(); it!= rozklad_drog[i].end(); it++) {
					ile_drog_tab[*it]--;
				}
			}
		}
	} while (byla_zmiana);
//	for (int i = 1; i <= ile_miast; i++)
//		cout << "miasto" << i << " = " << ile_drog_tab[i] << endl;
	
	int i = 1;
	list<int> kandydaci[ile_miast];
	int ile_kandydatow = 0;
	int indeks;
	stack<int> stos;
	while (i <= ile_miast && ile_drog_tab[i] <= -1)
		i++;
	while (i <= ile_miast) {

		kandydaci[ile_kandydatow].push_front(i);
		stos.push(i);
		while(!stos.empty()) {
			indeks = stos.top();
			stos.pop();
			ile_drog_tab[indeks] = -1;
			for(auto it = rozklad_drog[indeks].begin(); it != rozklad_drog[indeks].end(); it++){
				if (ile_drog_tab[*it] > -1) {
					stos.push(*it);
					ile_drog_tab[*it] = -1;
					kandydaci[ile_kandydatow].push_front(*it);
				}
			}
		}
		ile_kandydatow++;
		while (i <= ile_miast && ile_drog_tab[i] <= -1)
			i++;
	}
	int najlepsi = 0;
	for (int j = 0; j < ile_miast; j++) {
		if (kandydaci[j].size() > kandydaci[najlepsi].size())
			najlepsi = j;
	}
	kandydaci[najlepsi].sort();
	if (kandydaci[najlepsi].size() != 0) {
		cout << kandydaci[najlepsi].size() << endl;
		unsigned int ktory_obrot = 1;
		for (auto it = kandydaci[najlepsi].begin(); it != kandydaci[najlepsi].end(); it++) {
			cout << *it;
			if (ktory_obrot != kandydaci[najlepsi].size())
				cout << " ";
			
		}
	}
	else
		cout << "NIE";
	cout << endl;
	return 0;
}