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, ncycle = 0;
- vi p, color; // parents, color
- vvi cycle, g; // all cycles, graph
- int add_cycle(int cycle_end, int cycle_st) {
- // очистить, так как мог быть сохранен не цикл
- cycle[ncycle].clear();
- // через предков восстановить цикл
- cycle[ncycle].push_back(cycle_st);
- for (int v=cycle_end; v!=cycle_st; v=p[v])
- cycle[ncycle].push_back(v);
- cycle[ncycle].push_back(cycle_st);
- reverse(cycle[ncycle].begin(), cycle[ncycle].end());
- return cycle[ncycle].size();
- }
- 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) {
- // неориентированный граф
- // избавляюсь от вырожденности (v - to - v)
- if (add_cycle(v, to) > 3)
- ncycle++;
- }
- }
- color[v] = 0;
- }
- int main() {
- int n=0; cin >> n;
- g.assign(n + 1, vi());
- cycle.assign(n + 1, vi());
- 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] == -1)
- dfs(i);
- cout << endl << ncycle << endl;
- }
- /*
- 5
- 1 2
- 1 3
- 2 3
- 2 4
- 3 4
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement