Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <algorithm>
- #include <iostream>
- using namespace std;
- vector <int> tin;
- vector <int> up;
- vector <bool> was;
- vector <vector<int>> gr;
- vector <bool> cut_p;
- int P = 0;
- void dfs(int v, int last, int timer) {
- was[v] = true;
- tin[v] = up[v] = timer;
- int child = 0;
- for (int u: gr[v]){
- if (u == last) {
- continue;
- }
- else if (was[u] == true){
- up[v] = min(up[v], tin[u]);
- }
- else if (was[u] == false){
- dfs(u, v, timer + 1);
- up[v] = min(up[v], up[u]);
- if (up[u] >= tin[v] && v != last){
- if (!cut_p[v]) P++;
- cut_p[v] = true;
- }
- child++;
- }
- }
- if (v == last && child > 1) {
- if (!cut_p[v]) P++;
- cut_p[v] = true;
- }
- }
- int main()
- {
- int n, m;
- cin >> n >> m;
- gr.resize(n);
- cut_p.resize(n, false);
- for (int i = 0; i < m; ++i) {
- int a, b;
- cin >> a >> b;
- a--;
- b--;
- gr[a].push_back(b);
- gr[b].push_back(a);
- }
- tin.resize(n, -4);
- up.resize(n, 1e9);
- was.resize(n, false);
- dfs(0, 0, 0);
- cout << P<< '\n';
- for (int i= 0;i<n;++i){
- if (cut_p[i]){
- cout<<i+1<<'\n';
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement