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
#include <cstdio>
#include <cstdint>
#include <list>
#include <stack>
#include <cassert>

const static bool debug = false;
#define DEBUG(fmt, args...) do {\
	if (debug) {\
		fprintf(stderr, "%s: " #args " " fmt, __func__, args);\
		fflush(stderr);\
	} } while(0)

const static uint32_t MAX_N = 500000;

std::list<uint32_t> E[MAX_N + 1];
bool visited[MAX_N + 1];	// odwiedzony (szary)
bool done[MAX_N + 1];		// odwiedzeni wszyscy potomkowie (czarny)
uint32_t C[MAX_N + 1];		// licznik cyklów dla wierzchołków

std::list<uint32_t> T;		// trasa
std::stack<uint32_t> S;

int main() {
	uint32_t n, m, a, b;
	scanf("%lu %lu", &n, &m);
	for (uint32_t i = 0; i < m; ++i) {
		scanf("%lu %lu", &a, &b);
		E[a].push_back(b);
	}

	uint32_t cyclesNum = 0;		// liczba wszystkich cykli
	uint32_t validNum = 0;		// liczba wierzchołków spełniających warunki
	for (uint32_t i = 1; i <= n; ++i) {
		if (visited[i])
			continue;

		S.push(i);

		while (!S.empty()) {
			uint32_t v = S.top();
			DEBUG("%lu\n", v);
			if (visited[v]) {
				DEBUG("-- %lu\n", v);
				S.pop();
				if (!done[v]) {
					assert(T.back() == v);
					T.pop_back();
					done[v] = true;
				}
				continue;
			}

			T.push_back(v);
			visited[v] = true;

			for (uint32_t w: E[v]) {
				// ścieżki z v -> w
				if (!done[w]) {
					if (visited[w]) {	// szary
						DEBUG("C %lu\n", w);
						// wykryliśmy cykl w grafie od w do v
						++cyclesNum;
						validNum = 0;
						std::list<uint32_t>::iterator it = T.end();
						do {
							--it;
							if (++C[*it] == cyclesNum)
								++validNum;
						} while (*it != w);

						if (!validNum) {
							printf("0\n");
							return 0;
						}
					} else {	// biały
						DEBUG("S %lu\n", w);
						S.push(w);
					}
				}
			}
		}
	}


	if (cyclesNum == 0) {
		printf("NIE");
	} else {
		printf("%lu\n", validNum);
		for (uint32_t i = 1; i <= n; ++i) {
			if (C[i] == cyclesNum)
				printf("%lu ", i);
		}
	}
	return 0;
}