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
#include <iostream>
#include <vector>
using namespace std;

int liczba_cykli = 0, czesc_wspolna_wielkosc = 0, czesc_wspolna_start = -1;
vector<int> stan_wierzcholkow(0, -1);
bool exited = false;
vector<int> dalej(0);
vector<int> czesc_wspolna_dalej(0);

void dfs(int v, vector< vector<int> > &G){
    //cout <<"DFS przed przetworzeniem wierzcholka "<< v << endl;
    //for(int i = 1; i < stan_wierzcholkow.size(); i++)
    //    cout << stan_wierzcholkow[i]<<" ";
    //cout<<endl;
    //cout <<"liczba cyki i czesc wspolna: "<< liczba_cykli <<" " <<czesc_wspolna_wielkosc<<endl;
    //int a;
    //cin >> a;
    if(stan_wierzcholkow[v] >= 0){
        int u = dalej[v];
        int czesc_wspolna_wczesniej;
        if(stan_wierzcholkow[v] == liczba_cykli){
            czesc_wspolna_wielkosc = 1;
            czesc_wspolna_start = v;
            czesc_wspolna_wczesniej = v;
        }
        else
            czesc_wspolna_wielkosc = 0;
        stan_wierzcholkow[v]++;
        while(u != v){
            if(stan_wierzcholkow[u] == liczba_cykli){
                if(czesc_wspolna_wielkosc == 0)
                    czesc_wspolna_start = u;
                czesc_wspolna_dalej[czesc_wspolna_wczesniej] = u;
                czesc_wspolna_wczesniej = u;
                stan_wierzcholkow[u]++;
                czesc_wspolna_wielkosc++;
            }
            u = dalej[u];
        }
        liczba_cykli++;
        if(czesc_wspolna_wielkosc == 0){
            exited = true;
        }
        return;
    }
    else
        stan_wierzcholkow[v] = 0;
    for(int l = 0; l < G[v].size(); l++)
        if(stan_wierzcholkow[G[v][l]] > -2){
            dalej[v] = G[v][l];
            dfs(G[v][l], G);
            if(exited)
                return;
        }
    if(stan_wierzcholkow[v] <=0)
        stan_wierzcholkow[v] = -2;
}

int main(){
    ios_base::sync_with_stdio(0);
    int a, b, n, m;
    cin >> n >> m;
    vector< vector<int> >G(n+1, vector<int>(0));
    for(int i =0; i < m; i++){
        cin >> a >> b;
        G[a].push_back(b);
    }
    czesc_wspolna_dalej.resize(n+1, -1);
    dalej.resize(n+1, -1);
    stan_wierzcholkow.resize(n+1, -1);
    //for(int i =1 ;i <=n; i++)
    //    cout << stan_wierzcholkow[i] <<" ";
    for(int i = 1; i <= n; i++)
        if(stan_wierzcholkow[i] == -1)
            dfs(i, G);

    if(liczba_cykli == 0)
        cout << "NIE";
    else{
        cout << czesc_wspolna_wielkosc<< endl;
        vector<bool> wynik(n+1, false);

        for(int i = 0; i < czesc_wspolna_wielkosc; i++){
            wynik[czesc_wspolna_start] = true;
            czesc_wspolna_start = czesc_wspolna_dalej[czesc_wspolna_start];
        }
        for(int i = 1; i <= n+1; ++i)
            if(wynik[i])
                cout << i << " ";
    }
}