Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void dfs(ll u, ll p)
- {
- vis[u] = 1;
- lvl[u] = low[u] = 1 + lvl[p];
- ll child = 0;
- for(ll v : g[u])
- {
- if(v == p) continue;
- if(!vis[v])
- {
- child++;
- dfs(v, u);
- if(u == 1) { // root case
- ap[u] = (ap[u] | child > 1);
- }
- else if(low[v] >= lvl[u]) {
- ap[u] = 1;
- }
- low[u] = min(low[u], low[v]);
- }
- else {
- // back edge (u, v)
- // update with lvl[v], not low[v] because we can use only 1 back edge
- low[u] = min(low[u], lvl[v]);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment