#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; }
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; } |