SHARE
TWEET

Untitled

lalalalalalalaalalla Sep 14th, 2019 (edited) 104 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top