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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
/*
 * main.c
 *
 *  Created on: 29 wrz 2015
 *      Author: slawek
 */


#include <stdio.h>
#include <stdlib.h>

//#define DEBUG_1

#define CITYMAX	200000
#define ROUTEMAX 200000

struct nodelist {
	long cityno;
	struct nodelist *next;
};

struct citynode {
//	long city;	//nr miasta
	long routeno;	//ilosc drog wychodzacych z miasta
	long marking;	//do znalezienia skladowych spojnosci i czegos tam jeszcze
	struct nodelist *head;
};

struct citynode cities[CITYMAX+1]; //bedziemy sobie indeksować od 1, indeks to nr miasta
long markings[CITYMAX+1]; //tu bedziemy liczyc liczebnosci grup

long d; //parametr d

void append(long fromcity, long tocity);
void removecity(long city);
void connect(long city, long tomark);

int main()
{
	long n, m; //ilosc miast, ilosc drog
	long i;
	long a, b; //konce drogi
	long maxcnt = 0, maxmark = 0;

	scanf("%ld %ld %ld\n", &n, &m, &d);

	for(i=0; i<m; i++)
	{
		scanf("%ld %ld\n", &a, &b);
		append(a, b);
		append(b, a);

//		cities[a].city = a; //będzie potrzebne przy sortowaniu
//		cities[b].city = b;
	}
#ifdef DEBUG_1
	//test
	for(i=1; i<=n; i++)
	{
		printf("przed - %ld: %ld\n",i, cities[i].routeno);
	}//----
#endif
	for(i=1; i<=n; i++)
	{
		if(cities[i].routeno<d && cities[i].routeno  && !cities[i].marking)	//miasto nie spelnia 1. warunku skomunikowania
		{
			removecity(i);	//zeruje miasto i usuwa drogi wychodzące z miasta z listy dróg innych miast
		}
	}//musi być kilka przebiegów pętli - tak dlugo az nie bedzie miast <d

#ifdef DEBUG_1
	//test
	for(i=1; i<=n; i++)
	{
		printf("po - %ld: %ld\n",i,  cities[i].routeno);
	}//----
#endif

	//oznaczamy ewentualne rozlaczne zbiory S
	for(i=1; i<=n; i++)
	{
		if(cities[i].marking<=0 && cities[i].routeno)
		{
			connect(i,i);
		}
	}

#ifdef DEBUG_1
	//test
	for(i=1; i<=n; i++)
	{
		printf("polaczone - ind %ld: mark %ld - routes %ld\n",i,cities[i].marking, cities[i].routeno);
	}//----
#endif

	//sumujemy liczebnosc grup
	for(i=1; i<=n; i++)
	{
		if(cities[i].marking > 0)
			markings[cities[i].marking]++;
	}

#ifdef DEBUG_1
	//test
	for(i=1; i<=n; i++)
	{
	//	if(markings[i] > 0)
			printf("marking: mark %ld, ile %ld\n",i,markings[i]);
	}//----
#endif

	//znajdujemy najwieksza liczebnosc
	for(i=1; i<=n; i++)
	{
		if(markings[i] > maxcnt)
		{
			maxcnt = markings[i];
			maxmark = i;
		}

	}

#ifdef DEBUG_1
		printf("maxmark %ld, cnt %ld\n",maxmark,maxcnt);
#endif

		//wyprowadzenie wynikow
		if(maxmark == 0)
			printf("NIE\n");
		else
		{
			printf("%ld\n",maxcnt);
			for(i=1; i<=n; i++)
			{
				if(cities[i].marking==maxmark)
					printf("%ld ",i);
			}

		}

	return 0;
}


//********************************************

void append(long fromcity, long tocity)
{
	struct nodelist *tmp;

	tmp = malloc(sizeof(struct nodelist));
	tmp->cityno = tocity;
	tmp->next = cities[fromcity].head;
	cities[fromcity].head = tmp;
	cities[fromcity].routeno++;
}//----

void removeroute(long fromcity, long tocity);
void removecity(long city)
{
	long tmp;

	cities[city].marking = -1;
	while(cities[city].routeno)
	{
		tmp = cities[city].head->cityno; //pierwsze miasto na liście
		removeroute(city, tmp); //usunięcie drogi do miasta pierwszego na liscie
		cities[city].routeno--;  //zmiejszenie licznika liczby drog
		removeroute(tmp, city); //to samo w miescie do ktorego droga prowadzila
		cities[tmp].routeno--;  //zmiejszenie licznika liczby drog
		if(cities[tmp].routeno<d && cities[tmp].routeno && !cities[tmp].marking)
			removecity(tmp);
	}
}

void removeroute(long fromcity, long tocity)
{
	struct nodelist *i, **previ;

	for(i=cities[fromcity].head, previ=&cities[fromcity].head; i; previ=&(i->next), i=i->next)
	{
		if(i->cityno==tocity)
		{
			*previ = i->next; //przeskoczenie wskaźnika w liście
			free(i);	//usunięcie drogi
			//cities[fromcity].routeno--;  //zmiejszenie licznika liczby drog
			break;
		}
	}
}

//-----
void connect(long city, long tomark)
{
	long tmp;

	cities[city].marking = tomark;
	while(cities[city].head)
	{
		tmp = cities[city].head->cityno; //pierwsze miasto na liście
		removeroute(city, tmp); //usunięcie drogi do miasta pierwszego na liscie
		removeroute(tmp,city);
		if(cities[tmp].marking<=0)
			connect(tmp, tomark);
	}
}