Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void articulationDFS(int u, int &time)
- {
- int childrenCount = 0;
- lowest[u] = discovery[u] = ++time;
- visited[u] = true;
- for(auto v : adj[u])
- {
- if(!visited[v])
- {
- childrenCount++;
- parent[v] = u;
- articulationDFS(v, time);
- lowest[u] = std::min(lowest[u], lowest[v]);
- if((parent[u] != -1 && lowest[v] >= discovery[u]) || (parent[u] == -1 && childrenCount > 1))
- AP[u] = true;
- }
- else if(v != parent[u])
- lowest[u] = std::min(lowest[u], discovery[v]);
- }
- }
- std::vector<int> findArticulationPoints()
- {
- std::vector<int> articulationPoints;
- for(int i = 0; i < n; i++)
- {
- if(!visited[i])
- {
- int time = 0;
- articulationDFS(i, time);
- }
- }
- for(int i = 0; i < n; i++)
- if(AP[i])
- articulationPoints.push_back(i);
- return articulationPoints;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement