Advertisement
baalaandaa

Untitled

Jul 21st, 2021
321
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.00 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<vector<int> > g;
  6. vector<int> tin, fup, used;
  7. int timer = 0;
  8.  
  9. void dfs(int v, int p = -1){
  10. used[v] = 1;
  11. tin[v] = timer;
  12. fup[v] = tin[v];
  13. timer++;
  14. int ch = 0;
  15. for(auto to: g[v]){
  16. if(to == p) continue;
  17. if(used[to]) {
  18. fup[v] = min(fup[v], tin[to]);
  19. } else {
  20. dfs(to, v);
  21. ch++;
  22. fup[v] = min(fup[v], fup[to]);
  23. if(fup[to] >= tin[v] && p != -1){
  24. cout << v << endl;
  25. }
  26. }
  27. }
  28. if(ch > 1 && p == -1)
  29. cout << v << endl;
  30. }
  31.  
  32. signed main() {
  33. #ifdef DEBUG
  34. freopen("input.txt", "r", stdin);
  35. #endif
  36. int n, m;
  37. cin >> n >> m;
  38. g.resize(n);
  39. used.resize(n, 0);
  40. tin.resize(n, 0);
  41. fup.resize(n, 1e9+9);
  42. for(int i = 0; i < m; i++){
  43. int u, v;
  44. cin >> u >> v;
  45. u--, v--;
  46. g[u].push_back(v);
  47. g[v].push_back(u);
  48. }
  49. dfs(0);
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement