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
//usuwamy wierzcholki, ktore maja stopien mniejszy niz d dopoki nie ma juz takich wierzcholkow
//w powstalym podgrafie szukamy najliczniejszej skladowej

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main()
{
	int n, k, d, a, b;
	scanf("%d%d%d", &n, &k, &d);
	vector<int> v[n + 1];
	int degrees[n + 1], visited[n + 1];

	for (int i = 0; i <= n; i++)
	{
		degrees[i] = 0;
		visited[i] = 0;
	}

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

	//--- wrzucanie na kolejke wszystkich wierzcholkow o stopniu mniejszym niz d
	queue<int> q;

	for (int i = 1; i <= n; i++)
		if (degrees[i] < d)
		{
			visited[i] = 1;
			q.push(i);
		}

	//--- usuwanie wierzcholkow (ustawienie visited=1), ktorych stopien mniejszy niz d
	while (!q.empty())
	{
		int w = q.front();
		q.pop();
		for (int i = 0; i < v[w].size(); i++)
		{
			degrees[v[w][i]]--;
			if (visited[v[w][i]] == 0 && degrees[v[w][i]] < d)
			{
				visited[v[w][i]] = 1;
				q.push(v[w][i]);
			}
		}
		degrees[w] = 0;
	}

	//--- szukanie najliczniejszej skladowej z uwzglednieniem, ze niektore wierzcholki usuniete
	int maxN = 0, maxId = 0; //liczba wierzcholkow w najliczniejszej skladowej oraz identyfikator - miejsce w tablicy skladowe, gdzie zapisane sa wierzcholki skladowej
	vector<int> skladowe[n + 1];

	for (int i = 1; i <= n; i++)
		if (visited[i] == 0) //wierzcholek zachowal sie po sekcji usuwania, ale jeszcze nie nalezy do zadnej skladowej
		{//BFS, aby znalezc skladowa
			int counter = 0;
			q.push(i);
			visited[i] = 2; //oznaczenie wierzcholka wzietego juz do jakiejs skladowej

			while (!q.empty())
			{
				int w = q.front();
				q.pop();
				skladowe[i].push_back(w);

				for (int j = 0; j < v[w].size(); j++)
					if (visited[v[w][j]] == 0) //wierzcholek jeszcze nie wziety do skladowej ale odwiedzony
					{
						q.push(v[w][j]);
						visited[v[w][j]] = 2;
					}
			}

			if (maxN < skladowe[i].size())
			{ 
				maxN = skladowe[i].size();
				maxId = i;
			}
		}

	if (maxN <= 1)
		printf("NIE\n");
	else
	{
		sort(skladowe[maxId].begin(), skladowe[maxId].end());
		printf("%d\n", maxN);
		for (int i = 0; i < skladowe[maxId].size() - 1; i++)
			printf("%d ", skladowe[maxId][i]);
		printf("%d\n", skladowe[maxId][skladowe[maxId].size() - 1]);
	}
}