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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;

//#define PDEBUG

#define MAXN 200000

multimap<short int,short int> Drogi;

short int G[MAXN][3]; 	// kolumna 0 - ile drog; 1 - czy jest w docelowym zbiorze; 2 - w ktorej grupie
int n=0;				// ile wierzcholkow
int d;					// min ilosc drog z wierzcholka
int g=0;				// ile grup
int LG[MAXN];				// liczebnosc grupy - UWAGA - pierwsza grupa w LG[1]
int ilemax=0;			// ile miast w max grupie
int maxg=0;				// nr grupy max

void wczytaj_G()
{
	memset(G,0,3*MAXN);

	int k; 				// ile krawedzi
	int from, to;	// miasto poczatkowe i koncowe drogi
	scanf("%d %d %d", &n, &k, &d);	// ile miast / drog / min ilosc
	for (int i=0;i<k;i++) {
		scanf ("%d %d", &from, &to);	// wczytuje droge
		from--;to--;					// format OI
		Drogi.insert(pair<short int,short int>(from,to));
		Drogi.insert(pair<short int,short int>(to,from));
		G[from][0]++;					// zliczam ilosc drog z wiercholka from
		G[to][0]++;						// nadmiarowo - jw
	}
}

void drukuj_G(char* s=NULL)
{
#ifdef PDEBUG
	if (!s)
		printf("\n");
	else
		printf("%s\n",s);

	pair <multimap<short int, short int>::iterator, multimap<short int, short int>::iterator> ret;
	for (int i=0;i<n; i++) {
		ret = Drogi.equal_range(i);
		for (multimap<short int, short int>::iterator x=ret.first; x!=ret.second; x++)
			printf("%d-%d ", x->first, x->second);
		printf("\n");
		for (int j=0; j<3; j++)
			printf ("%d/", G[i][j]);
		printf("\n");
	}
#endif
}

int ile_drog(int i)
{
	return G[i][0];
}

void usun(int i) // usun miasto ze zbioru
{
	pair <multimap<short int, short int>::iterator, multimap<short int, short int>::iterator> ret;
	ret = Drogi.equal_range(i);				// sasiedzi i
	if (ret.first!=Drogi.end()) {			// jesli jakis jest
		G[i][0]-=Drogi.count(i);			// zmniejszam ilosc drog do i
		Drogi.erase(ret.first, ret.second);	// usuwam drogi z i
	}

	for (int j=0; j<n; j++) {				// dla sasiadow i usuwam drogi w druga strone....
		ret = Drogi.equal_range(j);			// sasiedzi j
		for (multimap<short int, short int>::iterator x=ret.first; x!=ret.second; x++)
			if (x->second==i) {				// prowadzi do i
				G[j][0]--;					// zmniejszam ilosc sasiadow j
				Drogi.erase(x);				// usuwam droge j do i
				if (ile_drog(j)<d) 			// jesli zostalo za malo drog - rekurencja
					usun(j);
				break;
			}
	}

	G[i][1]=0;								// usuwam ze zbioru
}

void dodaj(int i) // dodaj miasto do zbioru
{
	G[i][1]=1;
}

bool w_zbiorze(int i)
{
	return G[i][1];
}

bool w_grupie(int m)
{
	return (G[m][2]>0);
}

bool w_grupie(int m, int g)
{
	return (G[m][2]==g);
}

void do_grupy(int m, int g)
{
	G[m][2]=g;	// dodaj miasto do grupy
	LG[g]++;		// zwieksz ilosc miast
	if (LG[g]>ilemax) {
		ilemax=LG[g];
		maxg=g;
	}
}

void tworz_grupe(int m, int g)
{
	do_grupy(m, g);				// dodaje siebie do grupy
	for (int i=0; i<n; i++) {	// dla moich sasiadow
		if (w_zbiorze(i) and (not w_grupie(i))) // jesli w zbiorze ale jeszcze w zadnej grupie
			tworz_grupe(i,g);					// dodaje sasiada (i rekurencyjnie jego sasiadow) do grupy
	}
}

void utworz_grupy()
{
	g=1;						// grupa pierwsza
	LG[g]=0;					// liczebnosc grupy 1
	for (int m=0; m<n; m++) {	// kolejno dla wszystkich miast
		if (w_zbiorze(m) and (not w_grupie(m)))	// jesli w zbiorze ale jeszcze w zadnej grupie
			tworz_grupe(m,g);	// rekurencyjnie tworze nowa, spojna grupe miast
		g++;					// przygotowuje sie do kolejnej grupy
		LG[g]=0;
	}
}

void print_max()
{
	printf ("%d\n", ilemax);
	for (int i=0;i<n;i++) {
		if (w_grupie(i,maxg))
			printf ("%d ",i+1);	// format OI
	}
}

int main()
{
	wczytaj_G();
	drukuj_G();
	for (int i=0;i<n;i++)
		if (ile_drog(i)<d)	// sprawdz min wierzcholkow, wyrzuc ze zbioru niespelniajace
			usun(i);
		else
			dodaj(i);
	drukuj_G();

	utworz_grupy();
	drukuj_G();

	if (ilemax<=1)
		printf("NIE\n");
	else
		print_max();

	return 0;
}