#include <cstdio> #include <algorithm> #include <iomanip> #include <iostream> #include <vector> using namespace std; #define COLOR_BLACK "\x1b[30m" #define COLOR_RED "\x1b[31m" #define COLOR_GREEN "\x1b[32m" #define COLOR_YELLOW "\x1b[33m" #define COLOR_BLUE "\x1b[34m" #define COLOR_MAGENTA "\x1b[35m" #define COLOR_CYAN "\x1b[36m" #define COLOR_WHITE "\x1b[37m" #define COLOR_RESET "\x1b[0m" #define COLOR_BOLDBLACK "\033[1m\033[30m" #define COLOR_BOLDRED "\033[1m\033[31m" #define COLOR_BOLDGREEN "\033[1m\033[32m" #define COLOR_BOLDYELLOW "\033[1m\033[33m" #define COLOR_BOLDBLUE "\033[1m\033[34m" #define COLOR_BOLDMAGENTA "\033[1m\033[35m" #define COLOR_BOLDCYAN "\033[1m\033[36m" #define COLOR_BOLDWHITE "\033[1m\033[37m" const std::vector<const char*> colors{ COLOR_RED, COLOR_GREEN, COLOR_YELLOW, COLOR_BLUE, COLOR_MAGENTA, COLOR_CYAN, COLOR_BOLDRED, COLOR_BOLDGREEN, COLOR_BOLDYELLOW, COLOR_BOLDBLUE, COLOR_BOLDMAGENTA, COLOR_BOLDCYAN}; #define NDEBUG #ifndef NDEBUG #include <fstream> #include <cstring> struct MemChecker { ~MemChecker() { std::ifstream infile("/proc/self/status"); std::string line; while (std::getline(infile, line)) { if (line.compare(0, 6, "VmPeak") == 0) { int rv = 0; for (int i = 0; i < line.size(); ++i) { if (line[i] >= '0' && line[i] <= '9') { rv = 10 * rv + (line[i] - '0'); } } std::cerr << "memory: " << rv << " kB" << std::endl; return; } } std::cerr << "memory stats not found" << std::endl; } } __mem_checker; #define cdebug \ cerr << colors[std::hash<std::string>()(std::string(__func__)) % colors.size()] << __func__ << COLOR_RESET << ":" << __LINE__ << ": " #else class DebugStream {}; template <typename T> DebugStream& operator<<(DebugStream& s, T) { return s; } DebugStream cdebug; #endif constexpr int MAXN = 500010; constexpr int INF = 2000000000; int N; vector<int> neis[MAXN]; vector<int> results; vector<int> can_appends; int in_time[MAXN]; int out_time[MAXN]; int depth[MAXN]; int low[MAXN]; int high[MAXN]; int Time = 1; int EraStart = 1; void read_data() { int m; scanf("%d%d", &N, &m); while (m--) { int a, b; scanf("%d%d", &a, &b); neis[a - 1].push_back(b - 1); } fill(low, low + N, -1); fill(high, high + N, MAXN); } // @param can_append if you can append to "results" (i.e. if a cycle has been found) bool dfs(const int node, const bool can_append) { cdebug << "dfs(" << node << " [" << depth[node] << "], " << can_append << ") Time = " << Time << "\n"; in_time[node] = Time++; if (can_append) { can_appends.push_back(node); } bool my_rv = false; for (const auto nei : neis[node]) { cdebug << "[" << node << "] " << COLOR_BOLDRED << "nei " << nei << COLOR_RESET << "\n"; if (out_time[nei] > 0 && out_time[nei] < EraStart) { cdebug << "[" << node << "] nei " << nei << " WRONG ERA\n"; continue; } int remove_depth = -1; if (in_time[nei] == 0) { // tree edge; new node; out_time == 0 depth[nei] = depth[node] + 1; bool rv = dfs(nei, can_append && low[node] == -1); low[node] = max(low[node], low[nei]); high[node] = min(high[node], high[nei]); my_rv = my_rv || rv; if (rv && low[nei] > depth[node] && !can_append) { // found a cycle below, when there was already a cycle somewhere else // the result will be zero, period. cdebug << "cycle below detected when can_append == false, clearing and exiting\n"; results.clear(); break; } cdebug << "[" << node << "] updated lo hi to " << low[node] << " " << high[node] << "\n"; } else if (out_time[nei] == 0) { // up edge low[node] = max(low[node], depth[nei]); high[node] = min(high[node], depth[nei]); cdebug << "[" << node << "] UP EDGE updated lo hi to " << low[node] << " " << high[node] << "\n"; // remove everything results.clear(); my_rv = true; cdebug << "[" << node << "] removd ALL\n"; } else if (out_time[nei] < in_time[node]) { // skew edge low[node] = max(low[node], low[nei]); high[node] = min(high[node], high[nei]); cdebug << "[" << node << "] SKEW EDGE updated lo hi to " << low[node] << " " << high[node] << "\n"; cdebug << " can appends back: " << can_appends.back() << "\n"; // remove everything in the results above level depth[nei] it it reaches above their // lca (last node with can_append is sufficient) if (high[nei] <= depth[can_appends.back()]) { remove_depth = depth[nei]; } } else { // down_edge cdebug << "[" << node << "] DOWN EDGE low[nei] = " << low[nei] << " high[nei] = " << high[nei] << "\n"; if (high[nei] <= depth[node] && can_append) { remove_depth = depth[nei]; } } cdebug << "[" << node << "] REMOVING " << remove_depth << "\n"; while (!results.empty() && depth[results.back()] < remove_depth) { cdebug << "[" << node << "] removing " << results.back() << "\n"; results.pop_back(); } cdebug << "[" << node << "] REMOVEDDDDDD\n"; } cdebug << "[" << node << "] end rv = " << low[node] << " " << high[node] << " low " << low[node] << " out Time " << Time << "\n"; if (low[node] != -1 && low[node] <= depth[node] && can_append) { cdebug << "[" << node << "] appending\n"; results.push_back(node); } out_time[node] = Time++; if (can_appends.back() == node) { can_appends.pop_back(); } return my_rv; } bool find_cycles() { bool cycle_found = false; for (int i = 0; i < N; ++i) { if (in_time[i] > 0) { continue; } depth[i] = 1; EraStart = Time++; if (dfs(i, !cycle_found)) { if (cycle_found) { // cycles in different components results.clear(); return true; } else { cycle_found = true; } } } return cycle_found; } int main() { cerr.setf(ios::boolalpha); read_data(); if (find_cycles()) { sort(results.begin(), results.end()); printf("%d\n", results.size()); for (int r : results) { printf("%d ", r + 1); } if (!results.empty()) { printf("\n"); } } else { printf("NIE\n"); } }
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 | #include <cstdio> #include <algorithm> #include <iomanip> #include <iostream> #include <vector> using namespace std; #define COLOR_BLACK "\x1b[30m" #define COLOR_RED "\x1b[31m" #define COLOR_GREEN "\x1b[32m" #define COLOR_YELLOW "\x1b[33m" #define COLOR_BLUE "\x1b[34m" #define COLOR_MAGENTA "\x1b[35m" #define COLOR_CYAN "\x1b[36m" #define COLOR_WHITE "\x1b[37m" #define COLOR_RESET "\x1b[0m" #define COLOR_BOLDBLACK "\033[1m\033[30m" #define COLOR_BOLDRED "\033[1m\033[31m" #define COLOR_BOLDGREEN "\033[1m\033[32m" #define COLOR_BOLDYELLOW "\033[1m\033[33m" #define COLOR_BOLDBLUE "\033[1m\033[34m" #define COLOR_BOLDMAGENTA "\033[1m\033[35m" #define COLOR_BOLDCYAN "\033[1m\033[36m" #define COLOR_BOLDWHITE "\033[1m\033[37m" const std::vector<const char*> colors{ COLOR_RED, COLOR_GREEN, COLOR_YELLOW, COLOR_BLUE, COLOR_MAGENTA, COLOR_CYAN, COLOR_BOLDRED, COLOR_BOLDGREEN, COLOR_BOLDYELLOW, COLOR_BOLDBLUE, COLOR_BOLDMAGENTA, COLOR_BOLDCYAN}; #define NDEBUG #ifndef NDEBUG #include <fstream> #include <cstring> struct MemChecker { ~MemChecker() { std::ifstream infile("/proc/self/status"); std::string line; while (std::getline(infile, line)) { if (line.compare(0, 6, "VmPeak") == 0) { int rv = 0; for (int i = 0; i < line.size(); ++i) { if (line[i] >= '0' && line[i] <= '9') { rv = 10 * rv + (line[i] - '0'); } } std::cerr << "memory: " << rv << " kB" << std::endl; return; } } std::cerr << "memory stats not found" << std::endl; } } __mem_checker; #define cdebug \ cerr << colors[std::hash<std::string>()(std::string(__func__)) % colors.size()] << __func__ << COLOR_RESET << ":" << __LINE__ << ": " #else class DebugStream {}; template <typename T> DebugStream& operator<<(DebugStream& s, T) { return s; } DebugStream cdebug; #endif constexpr int MAXN = 500010; constexpr int INF = 2000000000; int N; vector<int> neis[MAXN]; vector<int> results; vector<int> can_appends; int in_time[MAXN]; int out_time[MAXN]; int depth[MAXN]; int low[MAXN]; int high[MAXN]; int Time = 1; int EraStart = 1; void read_data() { int m; scanf("%d%d", &N, &m); while (m--) { int a, b; scanf("%d%d", &a, &b); neis[a - 1].push_back(b - 1); } fill(low, low + N, -1); fill(high, high + N, MAXN); } // @param can_append if you can append to "results" (i.e. if a cycle has been found) bool dfs(const int node, const bool can_append) { cdebug << "dfs(" << node << " [" << depth[node] << "], " << can_append << ") Time = " << Time << "\n"; in_time[node] = Time++; if (can_append) { can_appends.push_back(node); } bool my_rv = false; for (const auto nei : neis[node]) { cdebug << "[" << node << "] " << COLOR_BOLDRED << "nei " << nei << COLOR_RESET << "\n"; if (out_time[nei] > 0 && out_time[nei] < EraStart) { cdebug << "[" << node << "] nei " << nei << " WRONG ERA\n"; continue; } int remove_depth = -1; if (in_time[nei] == 0) { // tree edge; new node; out_time == 0 depth[nei] = depth[node] + 1; bool rv = dfs(nei, can_append && low[node] == -1); low[node] = max(low[node], low[nei]); high[node] = min(high[node], high[nei]); my_rv = my_rv || rv; if (rv && low[nei] > depth[node] && !can_append) { // found a cycle below, when there was already a cycle somewhere else // the result will be zero, period. cdebug << "cycle below detected when can_append == false, clearing and exiting\n"; results.clear(); break; } cdebug << "[" << node << "] updated lo hi to " << low[node] << " " << high[node] << "\n"; } else if (out_time[nei] == 0) { // up edge low[node] = max(low[node], depth[nei]); high[node] = min(high[node], depth[nei]); cdebug << "[" << node << "] UP EDGE updated lo hi to " << low[node] << " " << high[node] << "\n"; // remove everything results.clear(); my_rv = true; cdebug << "[" << node << "] removd ALL\n"; } else if (out_time[nei] < in_time[node]) { // skew edge low[node] = max(low[node], low[nei]); high[node] = min(high[node], high[nei]); cdebug << "[" << node << "] SKEW EDGE updated lo hi to " << low[node] << " " << high[node] << "\n"; cdebug << " can appends back: " << can_appends.back() << "\n"; // remove everything in the results above level depth[nei] it it reaches above their // lca (last node with can_append is sufficient) if (high[nei] <= depth[can_appends.back()]) { remove_depth = depth[nei]; } } else { // down_edge cdebug << "[" << node << "] DOWN EDGE low[nei] = " << low[nei] << " high[nei] = " << high[nei] << "\n"; if (high[nei] <= depth[node] && can_append) { remove_depth = depth[nei]; } } cdebug << "[" << node << "] REMOVING " << remove_depth << "\n"; while (!results.empty() && depth[results.back()] < remove_depth) { cdebug << "[" << node << "] removing " << results.back() << "\n"; results.pop_back(); } cdebug << "[" << node << "] REMOVEDDDDDD\n"; } cdebug << "[" << node << "] end rv = " << low[node] << " " << high[node] << " low " << low[node] << " out Time " << Time << "\n"; if (low[node] != -1 && low[node] <= depth[node] && can_append) { cdebug << "[" << node << "] appending\n"; results.push_back(node); } out_time[node] = Time++; if (can_appends.back() == node) { can_appends.pop_back(); } return my_rv; } bool find_cycles() { bool cycle_found = false; for (int i = 0; i < N; ++i) { if (in_time[i] > 0) { continue; } depth[i] = 1; EraStart = Time++; if (dfs(i, !cycle_found)) { if (cycle_found) { // cycles in different components results.clear(); return true; } else { cycle_found = true; } } } return cycle_found; } int main() { cerr.setf(ios::boolalpha); read_data(); if (find_cycles()) { sort(results.begin(), results.end()); printf("%d\n", results.size()); for (int r : results) { printf("%d ", r + 1); } if (!results.empty()) { printf("\n"); } } else { printf("NIE\n"); } } |