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
#include <iostream>
#include <set>
#include <utility>
#include <vector>
#define FOR(i, beg, end) for (int i=beg; i<end; ++i)
#define FORSI(it, set) for (vset_t::iterator it=(set).begin(); it!=(set).end(); ++it)
using namespace std;

typedef int vert_t;
typedef vector<vert_t> vlist_t;
typedef set<vert_t> vset_t;
typedef vector<vset_t> graph_t;

inline bool needs_proc(vert_t);
void do_dfs(vert_t, vset_t& dest);

int n_vertices, n_edges, d_value;
graph_t graph;
vector<bool> dfs_seen;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	// reading input
	cin >>n_vertices >>n_edges >>d_value;
	graph.resize(n_vertices);
	FOR (i, 0, n_edges) {
		vert_t v1, v2;
		cin >>v1 >>v2;
		--v1, --v2;
		graph[v1].insert(v2);
		graph[v2].insert(v1);
	}

	// disconnect `bad` vertices
	vector<vert_t> bad_vs;
	FOR (v, 0, n_vertices)
		if (graph[v].size() < d_value)
			bad_vs.push_back(v);
	while (!bad_vs.empty()) {
		vert_t v = bad_vs.back();
		bad_vs.pop_back();
		vset_t& adjl = graph[v];
		FORSI (it, adjl)
			graph[*it].erase(v);
		adjl.clear();
	}

	// finding connected components
	// and the greatest of them
	vset_t maxset, tmps;
	dfs_seen.resize(n_vertices);
	FOR (v, 0, n_vertices)
		if (needs_proc(v)) {
			do_dfs(v, tmps);
			if (tmps.size() > maxset.size())
				maxset.swap(tmps);
			tmps.clear();
		}

	// print the result
	if (!maxset.empty()) {
		vset_t::iterator it;
		cout <<maxset.size() <<'\n';
		int i = 0;
		FORSI (it, maxset)
			cout <<*it+1 <<(i++ < maxset.size()-1? ' ':'\n');
	} else {
		cout <<"NIE\n";
	}
	return 0;
}

inline bool needs_proc(vert_t v)
{
	return !graph[v].empty() && !dfs_seen[v];
}

void do_dfs(vert_t v, vset_t& rset)
{
	dfs_seen[v] = true;
	rset.insert(v);

	vset_t& adjl = graph[v];
	FORSI (it, adjl) {
		vert_t v2 = *it;
		if (needs_proc(v2))
			do_dfs(v2, rset);
	}
}