Advertisement
lalalalalalalaalalla

Untitled

Sep 14th, 2019
163
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.71 KB | None | 0 0
  1. int n, timer = 0;
  2. vector<vector<int>> g; //g.resize(n);
  3. vector<int> tin, dp; //tin.resize(n); dp.resize(n);
  4. vector<bool> used; //used.assign(n, 0);
  5.  
  6. void dfs(int u, int p = -1) {
  7. used[u] = 1;
  8. tin[u] = dp[u] = timer++;
  9. int subt = 0;
  10. for (auto v: g[u]) {
  11. if (v == p) {
  12. continue;
  13. }
  14. if (used[v]) {
  15. dp[u] = min(dp[u], tin[v]);
  16. } else {
  17. dfs(v, u);
  18. dp[u] = min(dp[u], dp[v]);
  19. if (dp[v] >= tin[u] && p != -1) {
  20. // u - точка сочленения
  21. }
  22. subt++;
  23. }
  24. }
  25. if (p == -1 && subt >= 2) {
  26. // u - точка сочленения
  27. }
  28. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement