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

//#define DEBUG

#ifdef DEBUG
#define D(x) x
#else
#define D(x)
#endif

using namespace std;

struct Isn { // Intersection
  list<int> adj;
  bool critical;

  int marker;
  int current;
};

const int MAX_INTERSECTIONS = 500005;
Isn iss[MAX_INTERSECTIONS];
int N;
list<int> criticals;

void print_iss() {
  for(int i = 1; i <= N; i++) {
    printf("Intersection #%2d (%d/%d/%d): ", i, iss[i].critical, iss[i].marker, iss[i].current);
    list<int>::const_iterator it = iss[i].adj.begin();
    while(it != iss[i].adj.end()) {
      printf("%2d ", *it);
      it++;
    }
    printf("\n");
  }
}

int visit_and_find_cycle_start(int i, int parent_current) {
  if(iss[i].marker > 0) return 0;
  iss[i].marker = 1;
  iss[i].current = parent_current + 1;

  D(printf("visiting %d and it's %d node in path\n", i, iss[i].current);)

  list<int>::const_iterator it = iss[i].adj.begin();
  while(it != iss[i].adj.end()) {
    if(iss[*it].current > 0 && i != *it) {
      return *it;
    }
    int cycle_start = visit_and_find_cycle_start(*it, iss[i].current);
    if(cycle_start > 0) return cycle_start;
    it++;
  }

  iss[i].current = 0;
  return 0;
}


void get_any_cycle() {
  criticals.clear();
  for(int i = 1; i <= N; i++) {
    int cycle_start = visit_and_find_cycle_start(i, 0);
    if(cycle_start > 0) {
      D(printf("Found cycle starting @%d\n", cycle_start);)
      int step = cycle_start;
      do {
        D(printf("Adding %d to the cycle\n", step);)
        criticals.push_back(step);
        iss[step].critical = true;

        list<int>::const_iterator it = iss[step].adj.begin();
        while(it != iss[step].adj.end()) {
          if(iss[*it].current > 0) {
            step = *it;
            break;
          }
          it++;
        }
      } while(step != cycle_start);
      break;
    }
  }
}

void reset_iss() {
  for(int i = 1; i <= N; i++) {
    iss[i].marker = 0;
    iss[i].current = 0;
  }
}

void go(int i, int parent_current) {
  iss[i].marker = -1;
  iss[i].current = parent_current + 1;

  D(printf("going into %d and it's %d node in path, criticals size = %lu\n", i, iss[i].current, criticals.size());)
  list<int>::const_iterator it = iss[i].adj.begin();
  while(it != iss[i].adj.end()) {
    if(iss[*it].current > 0 && i != *it) { // cycle found
      int cycle_min_current = iss[*it].current;
      D(printf("Cycle found with min = %d\n", cycle_min_current);)
      list<int>::iterator cit = criticals.begin();
      while(cit != criticals.end()) {
        if(iss[*cit].current < cycle_min_current) {
          iss[*cit].critical = false;
          criticals.erase(cit);
        }
        cit++;
      }
    }
    if(iss[*it].marker != -1) go(*it, iss[i].current);
    it++;
  }
  iss[i].current = 0;
  iss[i].marker = i;
}

void go_through_all_cycles_and_remove_criticals() {
  reset_iss();
  for(int i = 1; i <= N; i++) {
    if(iss[i].marker == 0) go(i, 0);
  }
}

int main() {
  int m;
  scanf("%d %d", &N, &m);
  for(int i = 1; i <= N; i++) {
    iss[i] = (Isn){list<int>(), false, 0, 0};
  }

  for(int j = 1; j <= m; j++) {
    int a, b;
    scanf("%d %d", &a, &b);
    iss[a].adj.push_back(b);
  }

  D(print_iss();)
  D(printf("---\n");)
  get_any_cycle();

  D(printf("Any cycle size: %lu\n", criticals.size());)
  D(print_iss();)

  if(criticals.size() == 0) {
    printf("NIE\n");
    return 0;
  }

  go_through_all_cycles_and_remove_criticals();
  D(printf("=====\n");)
  D(print_iss();)
  D(printf("=====\n");)
  printf("%lu\n", criticals.size());
  for(int i = 1; i <= N; i++) {
    if(iss[i].critical) printf("%d ", i);
  }
  printf("\n");

  return 0;
}