Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Articulation Point of a graph. O(V+E).
- int Time[N] , low[N];
- int dfn= 0;
- void dfs(int u,int p )
- {
- Time[u] = low[u] = dfn ++;
- vis[u]=1;
- int cnt = 0;
- for(auto a: G[u]) {
- if(a==p) continue;
- if(vis[a]) {
- low[u] = min(low[u] , Time[a]);
- }
- else {
- dfs(a,u);
- if(low[a] >= Time[u] ) {
- isAp[u]=1;
- }
- low[u] = min(low[u] , low[a]);
- cnt ++;
- }
- }
- if(p==-1) {
- isAp[u] = (cnt>1);
- }
- }
Add Comment
Please, Sign In to add comment