Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int n, timer = 0;
- vector<vector<int>> g; //g.resize(n);
- vector<int> tin, dp; //tin.resize(n); dp.resize(n);
- vector<bool> used; //used.assign(n, 0);
- void dfs(int u, int p = -1) {
- used[u] = 1;
- tin[u] = dp[u] = timer++;
- int subt = 0;
- for (auto v: g[u]) {
- if (v == p) {
- continue;
- }
- if (used[v]) {
- dp[u] = min(dp[u], tin[v]);
- } else {
- dfs(v, u);
- dp[u] = min(dp[u], dp[v]);
- if (dp[v] >= tin[u] && p != -1) {
- // u - точка сочленения
- }
- subt++;
- }
- }
- if (p == -1 && subt >= 2) {
- // u - точка сочленения
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement