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
#include <stdio.h>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <algorithm>
#include <assert.h>

#define MAX_NODES 500050
#define START 1
#define FINISH 2
#define MAX_VAL 1000000000

#define DEBUG 0

typedef std::pair<int, int> IntPair;
typedef std::pair<int, std::map<int,int>* > RetPair;


char visited [MAX_NODES];
char onStack [MAX_NODES];
int  depths [MAX_NODES];
int  inCyclePos [MAX_NODES];
int  lastPosInCycleHit [MAX_NODES];

int max(int a, int b){
	return a > b ? a: b;
}

int min(int a, int b){
	return a < b ? a: b;
}

void printStack(std::vector<int> & dfsStack){
	for(int i = 0; i < (int)dfsStack.size(); i++) printf("%d ", dfsStack[i]);
	printf("\n");
}


void removeAllElementsFromTo(std::map<int, int> * firstCycleNodes, int lastElementFromCycle, int lastElementPos){
	//assert(lastElementFromCycle > -1);
	if (lastElementFromCycle  < lastElementPos){
		if (DEBUG) printf("USUWAMY SRODEK %d %d\n", lastElementFromCycle,lastElementPos);
	} else {
		if (DEBUG) printf("NIE USUWAMY SRODKA  %d %d gdyz cykl biegnie przeciwnie\n", lastElementFromCycle,lastElementPos);
		return;
	}
	std::map<int, int>::iterator itBottom = firstCycleNodes->upper_bound(lastElementFromCycle);
	std::map<int, int>::iterator itUpper = firstCycleNodes->lower_bound(lastElementPos);
	firstCycleNodes->erase(itBottom, itUpper);
}

void leftAllElementsFromTo(std::map<int, int> *firstCycleNodes, int lastElementFromCycle, int lastElementPos){
	if (DEBUG) printf("ZOSTAWIAMY SRODEK %d %d\n", lastElementPos,lastElementFromCycle);
	if (lastElementPos > -1){
		std::map<int, int>::iterator itBottom = firstCycleNodes->lower_bound(lastElementPos);
		firstCycleNodes->erase(firstCycleNodes->begin(), itBottom);
	}
	if (lastElementFromCycle > -1){
		std::map<int, int>::iterator itUpper = firstCycleNodes->upper_bound(lastElementFromCycle);
		firstCycleNodes->erase(itUpper, firstCycleNodes->end());
	}
}

void dumpCollections(std::map<int, int> * firstCycleNodes, std::vector<int> & dfsStack){
	printf("CYCLE MAP: ");
	for(std::map<int,int>::iterator it = firstCycleNodes->begin(); it != firstCycleNodes->end(); it++){
		printf("(v=%d pos %d) ",it->second,it->first);
	}
	printf("\nDFS STACK: ");
	for(int i = 0; i < (int) dfsStack.size(); i++){
		printf("%d ",dfsStack[i]);
	}
	printf("\n");
}

RetPair launchDFS(std::vector<std::vector<int> > & graph, int start){
	if (DEBUG) printf("START %d\n",start);
	memset(onStack, 0, MAX_NODES);
	std::vector<IntPair> stack;
	std::vector<int> dfsStack;
	std::map<int, int> * firstCycleNodes = new std::map<int, int> ();
	stack.push_back(IntPair(start,START));
	onStack[start] = 1;

	//opisujace pozycje na stosie
	int lastElementCycleDepth = -1;
	int firstElementInCycleDepht = -1;
	//int lastIndex = MAX_VAL;
	int foundCycle = 0;
	while(!stack.empty() && !(foundCycle == 1 && firstCycleNodes->empty())){
		IntPair next = stack.back();
		stack.pop_back();
		if (next.second == FINISH){
			onStack[next.first] = 0;
			if (DEBUG) printf("KONCZY %d\n",next.first);
			//tutaj nalezy przeleciec po wszystkich swoich dzieciach i zebrac najstarszego w cyklu
			if (inCyclePos[next.first] == -1)//przeliczamy to tylko wtedy jesli sami nie jestesmy w cyklu
				for(int i = 0; i < (int)graph[next.first].size(); i++) lastPosInCycleHit[next.first] = max(lastPosInCycleHit[next.first], lastPosInCycleHit[graph[next.first][i]]);
			if (inCyclePos[next.first] > -1){//to co zdejmujemy jest w naszym cyklu to musimy sie o jeden cofnac
				lastElementCycleDepth--;
			}
			dfsStack.pop_back();
			if (DEBUG) printStack(dfsStack);
			continue;
		}
		if (DEBUG) printf("PRZETWARZA %d=====\n",next.first);
		if (visited[next.first] == 1) {
			//tu byc moze istnieje cykl
			if (onStack[next.first] == 1){
				if (DEBUG) printf("ZNALAZL CYKL  DO %d na glebokosci %d \n", next.first,depths[next.first] );
				if (foundCycle == 0){///1111111111111111
					if (DEBUG) printf("OPCJA 1\n");
					foundCycle = 1;
					lastElementCycleDepth = dfsStack.size() - 1;//ostatni element cyklu na stosie
					firstElementInCycleDepht = dfsStack.size()- 1;//pierwszy element na stosie
					for(int i = (int)dfsStack.size() - 1; i >=0 ; i--){
						inCyclePos[dfsStack[i]] = i;//tu nie musimy indeksowac od zera
						lastPosInCycleHit[dfsStack[i]] = i;
						firstCycleNodes->insert(IntPair(i, dfsStack[i]));

						if (dfsStack[i] == next.first) break;//jesli docieramy do ostatneigo to sie zatrzymujemy
						firstElementInCycleDepht--;
					}
				} else {//tutaj jest sytuacja znalezienia kolejnego cyklu pomiedyz konkretymy punktami, 222222222222222
					if (DEBUG) printf("OPCJA (2) %d %d %d\n",next.first,lastElementCycleDepth, inCyclePos[next.first]);
					//removeNodes(firstCycleNodes, dfsStack, next.first);
					if (inCyclePos[next.first] == -1 && lastElementCycleDepth < depths[next.first]){//to oznacza ze trafilismy na cykl w zupelnie innym miejcu
						if (DEBUG) printf("CZYSCIMY\n");
						firstCycleNodes->clear();
					} else
						leftAllElementsFromTo(firstCycleNodes, lastElementCycleDepth,inCyclePos[next.first]);
				}
			} else	if (lastPosInCycleHit[next.first] > -1 && lastElementCycleDepth >= firstElementInCycleDepht){//33333333333333333
				if (DEBUG) printf("OPCJA (3) %d %d %d gl. pierwszy el cyklu %d\n",next.first,lastElementCycleDepth,lastPosInCycleHit[next.first], firstElementInCycleDepht);
				//trafilismy w wierzcholek bedacy w cyklu, albo wierzcholke ktory wiedzie do cyklu
				//sprawdzamy czy mamy czesc wspolna wczesniej, jesli tak to znalezlismy obejcie i miedzy punktami usuwamy elementy
				removeAllElementsFromTo(firstCycleNodes, lastElementCycleDepth,lastPosInCycleHit[next.first]);
			}
			if (DEBUG) dumpCollections(firstCycleNodes, dfsStack);
			continue;
		}

		dfsStack.push_back(next.first);
		depths[next.first] = dfsStack.size() - 1;//potrzebujemy informacji o glebokosci
		stack.push_back(IntPair(next.first,FINISH));
		onStack[next.first] = 1;
		if (DEBUG) dumpCollections(firstCycleNodes, dfsStack);
		if (DEBUG) printf("WCHODZI DO %d\n",next.first);
		if (DEBUG) printStack(dfsStack);
		visited[next.first] = 1;
		for(int i = 0; i < (int)graph[next.first].size(); i++){
			stack.push_back(IntPair(graph[next.first][i],START));
		}
	}
	return (RetPair(foundCycle, firstCycleNodes));
}


int main(){
	int v,e;
	int p,k;
	scanf("%d %d", &v, &e);
	std::vector<std::vector<int> > graph(v+1,std::vector<int> ());
	for(int i = 0; i < e; i++){
		scanf("%d %d",&p,&k);
		graph[p].push_back(k);
	}

	int starts = 0;
	memset(visited, 0, MAX_NODES);
	memset(inCyclePos, -1, MAX_NODES * sizeof(int));
	memset(lastPosInCycleHit, -1, MAX_NODES * sizeof(int));
	int cycle = 0;
	RetPair ret;
	RetPair retTmp;
	for(int i = 1; i <= v;i++){
		if (visited[i] == 0) {
			starts++;
			retTmp = launchDFS(graph, i);
			cycle += retTmp.first;
		}
		if (cycle == 2){
			printf("0\n");
			return 0;
		}
		if (retTmp.first == 1) ret = retTmp;
	}
	if (cycle == 0){
		printf("NIE\n");
	} else {
		printf("%d\n", (int)ret.second->size());
		std::vector<int>  toSort;
		for(std::map<int,int>::iterator it = ret.second->begin(); it != ret.second->end(); it++){
			toSort.push_back(it->second);
		}
		std::sort(toSort.begin(), toSort.end());
		for(int i = 0; i < (int) toSort.size(); i++){
			printf("%d ",toSort[i]);
		}
		printf("\n");
	}

	return 0;
}