Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef vector<bool> vb;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- int n=0;
- vi p, color; // parents, color
- vvi g; // all cycles, graph
- set<vi> cycle, box;
- void add_cycle(int cycle_end, int cycle_st) {
- vi curr_cycle, sorted;
- curr_cycle.push_back(cycle_st);
- for (int v=cycle_end; v!=cycle_st; v=p[v])
- curr_cycle.push_back(v);
- sorted = curr_cycle; // создать копию без последнего элемента
- curr_cycle.push_back(cycle_st);
- // reverse(curr_cycle.begin(), curr_cycle.end()); // не обязательно
- sort (sorted.begin(), sorted.end());
- // неориентированный граф
- // избавляюсь от вырожденности (v - to - v)
- if (curr_cycle.size()>3 && count(box.begin(), box.end(), sorted)==0) {
- cycle.insert(curr_cycle);
- box.insert(sorted);
- }
- }
- void dfs(int v) {
- color[v] = 1;
- for (int to: g[v]) {
- if (color[to] == 0) {
- p[to] = v;
- dfs(to);
- } else if (color[to] == 1) {
- add_cycle(v, to);
- }
- }
- color[v] = 0;
- }
- int main() {
- int n=0; cin >> n;
- g.assign(n + 1, vi());
- p.assign(n + 1, 0);
- color.assign(n + 1, 0);
- for (int i=1; i<=n; i++) {
- int v=0, u=0; cin >> v >> u;
- g[v].push_back(u);
- g[u].push_back(v);
- }
- for (int i=1; i<=n; i++)
- if (color[i] == 0)
- dfs(i);
- for (auto cyc: cycle) {
- cout << '\n';
- for (auto v: cyc) cout << v << ' ';
- }
- }
- /*
- 5
- 1 2
- 1 3
- 2 3
- 2 4
- 3 4
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement