Advertisement
georgiy110802

Untitled

Feb 20th, 2022
665
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.41 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define all(a) (a).begin(), (a).end()
  3. #define ull unsigned long long
  4. #define ll long long
  5. #define ld long double
  6. #define PI 3.14159265358979323846
  7. using namespace std;
  8.  
  9. int n, m;
  10. vector<vector<int>> v;
  11. vector<int> used, tin, up;
  12. set<int> res;
  13. int t = 0;
  14.  
  15. void dfs(int u, int p) {
  16.     tin[u] = t;
  17.     up[u] = t++;
  18.     used[u] = 1;
  19.     int c = 0;
  20.     for (auto i : v[u]) {
  21.         if (i == p) continue;
  22.         if (used[i]) {
  23.             up[u] = min(tin[i], up[u]);
  24.         } else {
  25.             dfs(i, u);
  26.             up[u] = min(up[u], up[i]);
  27.             if (up[i] >= tin[u] && p != -1) {
  28.                 res.insert(u);
  29.             }
  30.             c++;
  31.         }
  32.     }
  33.     if (p == -1 && c > 1) {
  34.         res.insert(u);
  35.     }
  36. }
  37.  
  38. int main() {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(0); cout.tie(0);
  41.     // freopen("input.txt", "r", stdin);
  42.     // freopen("output.txt", "w", stdout);
  43.     cin >> n >> m;
  44.     v.resize(n);
  45.     used.resize(n);
  46.     tin.resize(n);
  47.     up.resize(n);
  48.     for (int i=0; i < m; ++i) {
  49.         int d1, d2;
  50.         cin >> d1 >> d2;
  51.         d2--; d1--;
  52.         if (d1 > d2) swap(d1, d2);
  53.         v[d1].push_back(d2);
  54.         v[d2].push_back(d1);
  55.     }
  56.     for (int i=0; i < n; ++i) {
  57.         if (!used[i]) {
  58.             dfs(i, -1);
  59.         }
  60.     }
  61.     cout << res.size() << '\n';
  62.     for (auto i : res) cout << i + 1 << " ";
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement