Salvens

B

Aug 12th, 2023
1,403
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.44 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <array>
  4. #include <vector>
  5. #include <numeric>
  6. #include <random>
  7. #include <chrono>
  8. #include <set>
  9. #include <map>
  10.  
  11. #define int long long
  12. using namespace std;
  13.  
  14. const long long INF = 1e9 + 7;
  15. const int MAXN = 2e4 + 1000;
  16. const int N = 1e5 + 10;
  17.  
  18. vector<vector<pair<int, int>>> g;
  19. array<int, MAXN> used, tin, up;
  20. int timer = 0;
  21. set<int> ans;
  22.  
  23. void dfs(int v, int e = -1) {
  24.     used[v] = true;
  25.     tin[v] = up[v] = timer++;
  26.     int child = 0;
  27.     for (auto [to, num]: g[v]) {
  28.         if (num == e) {
  29.             continue;
  30.         }
  31.         if (used[to]) {
  32.             up[v] = min(up[v], tin[to]);
  33.         } else {
  34.             dfs(to, num);
  35.             up[v] = min(up[v], up[to]);
  36.             if (up[to] >= tin[v] && e != -1) {
  37.                 ans.insert(v);
  38.             }
  39.             ++child;
  40.         }
  41.     }
  42.     if (e == -1 && child > 1) {
  43.         ans.insert(v);
  44.     }
  45. }
  46.  
  47. signed main() {
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(nullptr);
  50.  
  51.     int n, m;
  52.     cin >> n >> m;
  53.     g.resize(n);
  54.     for (int i = 0; i < m; ++i) {
  55.         int u, v;
  56.         cin >> u >> v;
  57.         --u, --v;
  58.         g[u].emplace_back(v, i);
  59.         g[v].emplace_back(u, i);
  60.     }
  61.  
  62.     for (int i = 0; i < n; ++i) {
  63.         if (!used[i]) {
  64.             dfs(i);
  65.         }
  66.     }
  67.     cout << ans.size() << '\n';
  68.     for (auto& i: ans) {
  69.         cout << i + 1 << '\n';
  70.     }
  71. }
  72.  
Advertisement
Add Comment
Please, Sign In to add comment