Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdio.h>
- vector <int> t_1;
- vector <int> t_2;
- int time_ = 0;
- int dfs(int v, vector <vector <int>> &g, vector <int> &visited, int count)
- {
- int p = -1;
- visited[v] = 1; //vertex has visited
- t_1[v] = t_2[v] = time_++;
- for (int i = 0; i < g[v].size(); i++)
- {
- int cur = /*...*/; //current vertex
- if (cur == p) continue;
- if (visited[cur]) t_2[v] = min(t_2[v], t_1[cur]);
- else
- {
- dfs_rec(cur, g, visited, count);
- t_2[v] = min(t_2[v], t_2[cur]);
- if (t_1[v] < t_2[cur]) count++;
- }
- }
- return count;
- }
- void dfs(int v, vector <vector <int>> &g, vector <int> &visited, int count)
- {
- int p = -1;
- visited[v] = 1; //vertex has visited
- t_1[v] = t_2[v] = time_++;
- for (int i = 0; i < g[v].size(); i++)
- {
- int cur = /*...*/; //current vertex
- if (cur == p) continue;
- if (visited[cur]) t_2[v] = min(t_2[v], t_1[cur]);
- else
- {
- dfs(cur, g, visited, count);
- t_2[v] = min(t_2[v], t_2[cur]);
- }
- }
- }
- int main()
- {
- vector <vector <int>> g;
- vector <int> visited; //1 - visited, 0 - not visited;
- int n, m;
- cin >> n; //vertexes
- cin >> m; //edges
- g.resize(n);
- visited.resize(n);
- t_1.resize(n);
- t_2.resize(n);
- int u, v, count = 0;
- for (int i = 0; i < m; i++)
- {
- cin >> u; //v_1
- cin >> v; //v_2
- g[u].push_back(v);
- g[v].push_back(u);
- }
- for (int i = 0; i < n; i++) visited[i] = 0;
- for (int i = 0; i < n; i++)
- {
- if (visited[i] == 0)
- dfs(i, g, visited, count);
- }
- cout << count;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement