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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
//
// Z dedykacją dla Karoli
//
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#include<queue>
#include<algorithm>

#ifndef DEBUG
#define NDEBUG
#endif
#include<assert.h>

#ifdef DEBUG
#define log(format, ...)     fprintf(stderr, format "\n", ##__VA_ARGS__)
#define ifdebug(x)           x
#else
#define log(...)
#define ifdebug(x)
#endif

using namespace std;

class Node;
class Edge;
class Group;

Node* node;
int nodes;
int iteration=0;

/** Klasa reprezentująca krawędź w grafie (drogę) */
class Edge {
public:
    Node* to;       //!< cel krawędzi
    Edge* next;     //!< następna krawędź w liście jednokierunkowej
public:
};



/** Klasa reprezetunjaca wierzchołęk (skrzyżowanie) */
class Node {
public:        // podstawowe informacje o wierzchołku
    int index;      //!< Indeks tego wierzchołka
    Edge* e;        //!< Lista krawędzi wychodzących z tego wierzchołka (dróg wychodzących z tego skrzyżowania)
    Edge* rev;      //!< Lista krawędzi wchodzących do tego wierzchołka (drogi przychodzące do tego skrzyżowania)
public:        // dane na potrzeby algorytmów
    int visited;    //!<- Informacja o tym, czy wierzchołek był odwiedzony
    int dist;       //!<- Odłegłość od początku
    int len;        //!<- Odłęgłość od końca (długość najkrótszej ścieżki do celu z tego wierzchołka)
    bool disabled;  //!<- Czy punkt jest wyłączony dla algorytmu
    Node* prev;     //!<- Krwędź z której nastąpilo przejście na potrzeby algorytmu szukania najkrótszej drogi
public:
    inline void init(int i) { e=NULL; rev=NULL; dist=INT_MAX; len=INT_MAX; prev=NULL; disabled=false; index=i; visited=0; }
    inline void addEdge(Edge* edge, Node* target) { edge->to=target; edge->next=e; e=edge; }
    inline void addRev(Edge* edge, Node* target) { edge->to=target; edge->next=rev; rev=edge; }
    inline void findMinClear() { prev=NULL; dist=INT_MAX; }
};

/**
 * Funkcja szukająca najkrótszej ścieżki w grafie, która zaczyna i kończy się w
 * podanym punkcie. Jeżeli ścieżka nie istnieje to zwracany jest false
 * jeżeli istnieje, to zwracany jest true i w res znajduje się ścieżka z wierzchołkami ze ścieżki bez ostatniego i pierwszego.
 */
bool findMinPath(vector<Node*> &res, Node* ss) {
    assert(ss!=NULL);
    assert(!ss->disabled);
    for(int i=1;i<=nodes;++i) node[i].findMinClear(); // czyścimy dane związne z przeglądaniem
    queue<Node*> q;
    q.push(ss);     // dodajemy startowy punkt
    ss->dist=0;
    while(!q.empty()) {
        Node* n=q.front();
        assert(n!=NULL);
        q.pop();

        for(Edge* e=n->e;e!=NULL;e=e->next) {   // przechodzimy po wszystkich krawędziach danego wierzchołka
            assert(e!=NULL);
            Node* t=e->to;
            assert(t!=NULL);
            if(t->disabled) continue;   // pomijamy wyłączone wierzchołki
            if(t==ss) { // znaleziony cykl do początku
                // odbudowa drogi
                res.clear();
                Node* i=n;
                for(;;) {
                    res.push_back(i);
                    if(i==ss) break;
                    i=i->prev;
                }
                log("Found min path (cycle) of size: %d (dist: %d)",res.size(),n->dist+1);
                assert(res.size()==n->dist+1);
                return true;
            }
            if(t->dist==INT_MAX) {  // wierzchołek jeszcze nie odwiedzony
                assert(t->prev==NULL);
                t->dist=n->dist+1;
                t->prev=n;
                q.push(t);
            }
        }
    }
    assert(q.empty());
    return false;   // przeszliśmy cały graf i nie udało znaleźć się naleźć drogi do punktu startu
}

/**
 * Funkcja wyszukająca cyklu w grafie, do którego można trafi z zadanego punktu.
 * Jeżeli udało się znaleźć cykl, to zwracany jest wierzchołek, który należy do tego cyklu.
 */
Node* findCycle(Node* n) {
    assert(n!=NULL);
    //assert(!n->disabled);

    if(n->visited==-iteration) return n;    // odwiedzony przez te rekurencyjne wywołanie, a więc jest cykl
    if(n->visited==iteration) return NULL;  // już odwiedzano w innym wywołaniu, nie sprawdzamy koleny raz

    n->visited=-iteration;                  // oznaczamy tymczasowo

    for(Edge* e=n->e; e!=NULL; e=e->next) {
        assert(e!=NULL);
        Node* t=e->to;
        assert(t!=NULL);
        if(t->disabled) continue;   // pomijamy wyłączone wierzchołki
        t=findCycle(t);
        if(t!=NULL) {
            n->visited=iteration;   // na koniec oznaczamy, że byliśmy, aby był porządek
            return t;
        }
    }
    n->visited=iteration;       // oznaczamy, że byliśmy
    return NULL;    // nie ma cyklu i nie ma ścieżek
}

/**
 * Funkcja szukająca jakiegokolwiek cyklu w grafie
 */
Node* findCycle() {
    ++iteration;

    for(int i=1;i<=nodes;++i) {
        Node* n=&node[i];
        if(n->disabled) continue;   // pomijamy wyłączone
        assert(n->visited!=-iteration);
        if(n->visited!=iteration) {
            n=findCycle(n);
            assert(node[i].visited==iteration);
            if(n!=NULL) return n;
        }
    }
    return NULL;    // nie znaleziono
}


bool indexOrderCmp(Node* a, Node* b){
    return a->index<b->index;
}

/**
 * Funkcja wypisująca wynik zgodnie z wymaganiami zadania
 */
void print(vector<Node*> points) {
    sort(points.begin(),points.end(),indexOrderCmp);
    printf("%d\n",points.size());
    if(points.size()>0) {
        for(int i=0;i<points.size();++i) printf("%d ",points[i]->index);
        printf("\n");
    }
}

int main(int argc, char** argv) {
    int m;

    // etap 0 - wczytanie danych
    scanf("%d %d",&nodes,&m);

    node=(Node*)malloc(sizeof(Node)*(nodes+1));
    for(int i=1;i<=nodes;++i) node[i].init(i);

    // wczytanie krawędzi
    Edge* edge=(Edge*)malloc(sizeof(Edge)*(m*2));   // x2 bo drogi powrotne
    for(int i=0;i<m;++i) {
        int a,b;
        scanf("%d %d",&a,&b);
        node[a].addEdge(&edge[i<<1],&node[b]);      // dodajemy krawędź wychodzącą
        node[b].addRev(&edge[(i<<1)+1],&node[a]);   // dodajemy krawędź przychodzącą
    }

    // Etap 1 - znalezienie jakiegoś cyklu w grafie (jednego)
    Node* s=NULL;   // punkt startowy do dalszego działa (reprezentatn jakiegoś cyklu)
    s=findCycle();
    if(s==NULL) {           // jeżeli żaden podgraf nie ma cyklu
        log("Didn't found any cycle");
        printf("NIE\n");    // to pochód zgodnie z opisem nie może się odbyć.
        return 0;
    }

    // Etap 2 - Dla jakiegokolwiek punktu z cyklu (S) szukamy dla niego najmniejszego cyklu od S do S.
    vector<Node*> cycle;
    {
        log("Searching for cycle path at point: %d",s->index);
        bool res=findMinPath(cycle,s); // to powinno zawsze zwrócić prawdę, bo cykl jest, więc zawsze on może być najmniejszy
        assert(res);
        assert(cycle.size()>0);
    }
    log("Min cycle from node %d has %d points",s->index, cycle.size());
#ifdef DEBUG
    fprintf(stderr,"Cycle points: ");
    for(int i=cycle.size()-1;i>=0;--i) fprintf(stderr,"%d ",cycle[i]->index);
    fprintf(stderr,"\n");
#endif
    if(cycle.size()==nodes) {   // jeżeli wyszystkie wierzchołki są w cyklu i jest on najmniejszy, to nie ma co więcej robić - jesto jedyna droga
        print(cycle);
        return 0;
    }

    // Etap 3 - Sprawdzamy, czy w grafie bez wierzchołków cyklu z etapu 1 są jakieś inne cykle
    // jeżeli tak, to koniec, bo są możliwe dwie odrębne drogi manifestacji, a więc nie ma
    // szansy na arbitralny wybór punktu (k=0).
    {
#ifdef DEBUG
        for(int i=1;i<=nodes;++i) assert(!node[i].disabled);
#endif // DEBUG
        for(int i=0;i<cycle.size();++i) cycle[i]->disabled=true;    // wyłączamy

        if(findCycle()!=NULL) { // jeżeli znaleziono inny cykl, a obecny jest wyłączony, to znaczy że są rozłączne cykle i tym samym manifestacja może być w jednym z nich.
            printf("0\n");
            return 0;
        }

        for(int i=0;i<cycle.size();++i) cycle[i]->disabled=false;    // włączamy ponownie
#ifdef DEBUG
        for(int i=1;i<=nodes;++i) assert(!node[i].disabled);
#endif // DEBUG

    }

    // Etap 4 - jeżeli w grafie nie ma innych (rozłącznych) cykli, to pozostałe cykle w jakiś sposób na siebie nachodzą
    // sprawdzamy czy zabierając kolejne punktu z cyklu z etapu 0 uniemożliwmy wykonanie cyklu
    // jeżeli tak, to taki punkt jest jednym z punktów wynikowych (k++), bo każdy cykl w grafie przez niego przechodzi
    {
        vector<Node*> result;
        for(int i=0;i<cycle.size();++i) {
            cycle[i]->disabled=true;
            log("Checkint without node %d",cycle[i]->index);

            // ponieważ ewentualny badany cykl ma wspólne wierzchołki z badanym
            // więc wystarczy szukać cyklu tylko od kolejnego punktu tego, bo on przechodzi przez wszystkie wierzchołki cyklu,
            // a więc interesujące nas punkty

            ++iteration;
            if(findCycle(cycle[i])==NULL) {
                log("Without node %d cannot found cycle then this node is always required (part of result)",cycle[i]->index);
                result.push_back(cycle[i]);
            }

            cycle[i]->disabled=false;
        }

        print(result);
    }

    return 0;
}