#include <cstdio> #include <vector> #include <list> #include <unordered_set> #include <set> #include <unordered_map> #include <map> #include <utility> using namespace std; namespace std { template <> struct hash<std::vector<int>> { size_t operator()(const vector<int>& v) const { std::hash<int> hasher; size_t seed = 0; for (int i : v) { seed ^= hasher(i) + 0x9e3779b9 + (seed<<6) + (seed>>2); } return seed; } }; } void dfs(int v, vector<list<int> > &ve, vector<int> &base_vector, map<int, int> &base_map, vector<pair<vector<int>, map<int, int> > > &cycles, set<vector<int> > pureCycles, map<int, list<int> > &name, set<int> &visited) { if (visited.find(v) != visited.end()) { if (base_map.find(v) != base_map.end()) { vector<int> cycle_vector (base_vector.begin() + (*(base_map.find(v))).second, base_vector.end()); cycle_vector.push_back(v); map<int, int> cycle_map; int i = 0; for (auto it = cycle_vector.begin(); it != cycle_vector.end(); ++it, ++i) { cycle_map.insert(pair<int, int> (*it, i)); name[*it].push_back(cycles.size()); } cycles.push_back(pair<vector<int>, map<int, int> > (cycle_vector, cycle_map)); pureCycles.insert(cycle_vector); } else { list<vector<int> > new_cycles; for (auto it = name[v].begin(); it != name[v].end(); ++it) { //printf("cycle %d %d\n", name[v].size(), cycles.size()); vector<int> cycle_vector = cycles[*it].first; map<int, int> cycle_map = cycles[*it].second; if (base_map.find(cycle_vector.back()) != base_map.end()) { vector<int> new_cycle_vector (base_vector.begin() + (*(base_map.find(cycle_vector.back()))).second, base_vector.end()); new_cycle_vector.insert(new_cycle_vector.end(), cycle_vector.begin() + (*(cycle_map.find(v))).second, cycle_vector.end()); new_cycles.push_back(new_cycle_vector); } else { //puts("else"); } } for (auto it = new_cycles.begin(); it != new_cycles.end(); ++it) { if (pureCycles.find(*it) == pureCycles.end()) { map<int, int> new_cycle_map; int i = 0; for (auto it2 = (*it).begin(); it2 != (*it).end(); ++it2, ++i) { new_cycle_map.insert(pair<int, int> (*it2, i)); name[*it2].push_back(cycles.size()); } cycles.push_back(pair<vector<int>, map<int, int> > (*it, new_cycle_map)); pureCycles.insert(*it); } } } // for (auto it = cycles.begin(); it != cycles.end(); ++it) { // printf("%d", (*it).first.size()); // puts(""); // } return; } visited.insert(v); base_vector.push_back(v); base_map.insert(pair<int, int> (v, base_map.size())); for (auto it = ve[v].begin(); it != ve[v].end(); ++it) { dfs(*it, ve, base_vector, base_map, cycles, pureCycles, name, visited); } base_vector.pop_back(); base_map.erase(v); } int main() { int n, m; scanf("%d %d", &n, &m); vector<list<int> > ve (n, list<int> ()); for (int i = 0; i < m; ++i) { int a, b; scanf("%d %d", &a, &b); --a; --b; ve[a].push_back(b); } vector<int> base_vector; map<int, int> base_map; vector<pair<vector<int>, map<int, int> > > cycles; set<vector<int> > pureCycles; map<int, list<int> > name; set<int> visited; for (int i = 0; i < n && visited.size() < n; ++i) { if (visited.find(i) == visited.end()) { dfs(i, ve, base_vector, base_map, cycles, pureCycles, name, visited); } } // for (auto it = cycles.begin(); it != cycles.end(); ++it) { // for (auto it2 = ((*it).first).begin(); it2 != ((*it).first).end(); ++it2) { // printf("%d ", (*it2)+1); // } // puts(""); // } if (cycles.size() > 0) { set<int> intersection (cycles.front().first.begin(), cycles.front().first.end()); for (auto it = cycles.begin(); it != cycles.end(); ++it) { set<int> new_intersection; for (auto it2 = intersection.begin(); it2 != intersection.end(); ++it2) { if ((*it).second.find(*it2) != (*it).second.end()) { new_intersection.insert(*it2); } } intersection = new_intersection; } printf("%d\n", intersection.size()); for (auto it = intersection.begin(); it != intersection.end(); ++it) { printf("%d ", (*it) + 1); } printf("\n"); } else { printf("NIE"); } 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 | #include <cstdio> #include <vector> #include <list> #include <unordered_set> #include <set> #include <unordered_map> #include <map> #include <utility> using namespace std; namespace std { template <> struct hash<std::vector<int>> { size_t operator()(const vector<int>& v) const { std::hash<int> hasher; size_t seed = 0; for (int i : v) { seed ^= hasher(i) + 0x9e3779b9 + (seed<<6) + (seed>>2); } return seed; } }; } void dfs(int v, vector<list<int> > &ve, vector<int> &base_vector, map<int, int> &base_map, vector<pair<vector<int>, map<int, int> > > &cycles, set<vector<int> > pureCycles, map<int, list<int> > &name, set<int> &visited) { if (visited.find(v) != visited.end()) { if (base_map.find(v) != base_map.end()) { vector<int> cycle_vector (base_vector.begin() + (*(base_map.find(v))).second, base_vector.end()); cycle_vector.push_back(v); map<int, int> cycle_map; int i = 0; for (auto it = cycle_vector.begin(); it != cycle_vector.end(); ++it, ++i) { cycle_map.insert(pair<int, int> (*it, i)); name[*it].push_back(cycles.size()); } cycles.push_back(pair<vector<int>, map<int, int> > (cycle_vector, cycle_map)); pureCycles.insert(cycle_vector); } else { list<vector<int> > new_cycles; for (auto it = name[v].begin(); it != name[v].end(); ++it) { //printf("cycle %d %d\n", name[v].size(), cycles.size()); vector<int> cycle_vector = cycles[*it].first; map<int, int> cycle_map = cycles[*it].second; if (base_map.find(cycle_vector.back()) != base_map.end()) { vector<int> new_cycle_vector (base_vector.begin() + (*(base_map.find(cycle_vector.back()))).second, base_vector.end()); new_cycle_vector.insert(new_cycle_vector.end(), cycle_vector.begin() + (*(cycle_map.find(v))).second, cycle_vector.end()); new_cycles.push_back(new_cycle_vector); } else { //puts("else"); } } for (auto it = new_cycles.begin(); it != new_cycles.end(); ++it) { if (pureCycles.find(*it) == pureCycles.end()) { map<int, int> new_cycle_map; int i = 0; for (auto it2 = (*it).begin(); it2 != (*it).end(); ++it2, ++i) { new_cycle_map.insert(pair<int, int> (*it2, i)); name[*it2].push_back(cycles.size()); } cycles.push_back(pair<vector<int>, map<int, int> > (*it, new_cycle_map)); pureCycles.insert(*it); } } } // for (auto it = cycles.begin(); it != cycles.end(); ++it) { // printf("%d", (*it).first.size()); // puts(""); // } return; } visited.insert(v); base_vector.push_back(v); base_map.insert(pair<int, int> (v, base_map.size())); for (auto it = ve[v].begin(); it != ve[v].end(); ++it) { dfs(*it, ve, base_vector, base_map, cycles, pureCycles, name, visited); } base_vector.pop_back(); base_map.erase(v); } int main() { int n, m; scanf("%d %d", &n, &m); vector<list<int> > ve (n, list<int> ()); for (int i = 0; i < m; ++i) { int a, b; scanf("%d %d", &a, &b); --a; --b; ve[a].push_back(b); } vector<int> base_vector; map<int, int> base_map; vector<pair<vector<int>, map<int, int> > > cycles; set<vector<int> > pureCycles; map<int, list<int> > name; set<int> visited; for (int i = 0; i < n && visited.size() < n; ++i) { if (visited.find(i) == visited.end()) { dfs(i, ve, base_vector, base_map, cycles, pureCycles, name, visited); } } // for (auto it = cycles.begin(); it != cycles.end(); ++it) { // for (auto it2 = ((*it).first).begin(); it2 != ((*it).first).end(); ++it2) { // printf("%d ", (*it2)+1); // } // puts(""); // } if (cycles.size() > 0) { set<int> intersection (cycles.front().first.begin(), cycles.front().first.end()); for (auto it = cycles.begin(); it != cycles.end(); ++it) { set<int> new_intersection; for (auto it2 = intersection.begin(); it2 != intersection.end(); ++it2) { if ((*it).second.find(*it2) != (*it).second.end()) { new_intersection.insert(*it2); } } intersection = new_intersection; } printf("%d\n", intersection.size()); for (auto it = intersection.begin(); it != intersection.end(); ++it) { printf("%d ", (*it) + 1); } printf("\n"); } else { printf("NIE"); } return 0; } |