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
#include <cstdio>
#include <queue>
#include <vector>

const int SIZE=200005;

struct vertex
{
	int 	size{0};
	bool 	color{false};
	int 	scc{0};
	std::vector<int> edges;
} Graph[SIZE];

int dfs(int start, int sccColor)
{
	int size{1};
	Graph[start].scc=sccColor;

	for(int v: Graph[start].edges)
		if(!Graph[v].scc && !Graph[v].color)
			size+=dfs(v, sccColor);

	return size;
}

int main(int argc, char const *argv[])
{
	std::queue<int> q;
	int n, m, d, a, b, FinalGraphSize{0};
	scanf("%d %d %d", &n, &m, &d);

	while(m--)
	{
		scanf("%d %d", &a, &b);
		Graph[a-1].edges.push_back(b-1);
		Graph[b-1].edges.push_back(a-1);
	}

	for (int i = 0; i < n; ++i)
	{
		Graph[i].size = Graph[i].edges.size();
		if (Graph[i].size<d)
		{
			Graph[i].color=true;
			q.push(i);
		}
	}

	int i;
	while(!q.empty())
	{
		i=q.front();
		q.pop();
		for (int x : Graph[i].edges)
		{
			Graph[x].size--;
			if(Graph[x].size<d && !Graph[x].color)
			{
				q.push(x);
				Graph[x].color=true;
			}
		}
	}

	int actualScc=1;
	int gscc=0;
	for (int i = 0; i < n; ++i)
	{
		if(!Graph[i].scc && !Graph[i].color)
		{
			int s = dfs(i, actualScc);
			if (FinalGraphSize < s)
			{
				gscc=actualScc;
				FinalGraphSize=s;
			}
			actualScc++;
		}
	}

	if (!FinalGraphSize)
		printf("NIE");
	else
	{
		printf("%d\n", FinalGraphSize);
		for (int i = 0; i < n; ++i)
		{
			if(Graph[i].scc == gscc)
				printf("%d ", i+1);
		}
	}
	printf("\n");
	return 0;
}