### searleser97's blog

By searleser97, 3 years ago,

# Articulation Points

Let's define what an articulation point is. We say that a vertex $V$ in a graph $G$ with $C$ connected components is an articulation point if its removal increases the number of connected components of $G$. In other words, let $C'$ be the number of connected components after removing vertex $V$, if $C' > C$ then $V$ is an articulation point.

## Naive approach O(V * (V + E))

For every vertex V in the graph G do
Remove V from G
if the number of connected components increases then V is an articulation point


## Tarjan's approach O(V + E)

First, we need to know that an ancestor of some node $V$ is a node $A$ that was discoverd before $V$ in a DFS traversal.

In the graph $G_1$ shown above, if we start our DFS from A and follow the path to C through B ( A -> B -> C ), then A is an ancestor of B and C in this spanning tree generated from the DFS traversal.

#### Example of DFS spanning trees of a graph

Now that we know the definition of ancestor let's dive into the main idea.

### Idea

Let's say there is a node $V$ in some graph $G$ that can be reached by a node $U$ through some intermediate nodes (maybe non intermediate nodes) following some DFS traversal, if $V$ can also be reached by $A$ = "ancestor of $U$" without passing through $U$ then, $U$ is NOT an articulation point because it means that if we remove $U$ from $G$ we can still reach $V$ from $A$, hence, the number of connected components will remain the same.

So, we can conclude that the only 2 conditions for $U$ to be an articulation point are:

1. If all paths from $A$ to $V$ require $U$ to be in the graph.

2. If $U$ is the root of the DFS traversal with at least 2 children subgraphs disconnected from each other.

Then we can break condition #1 into 2 subconditions:

• $U$ is an articulation point if it does not have an adyacent node $V$ that can reach $A$ without requiring $U$ to be in $G$.

• $U$ is an articulation point if it is the root of some cycle in the DFS traversal.

### Examples:

Here B is an articulation point because all paths from ancestors of B to C require B to be in the graph.

Here B is NOT an articulation point because there is at least one path from an ancestor of B to C which does not require B.

Here B is an articulation point since it has at least 2 children subgraphs disconnected from each other.

### Implementation

Well, first thing we need is a way to know if some node $A$ is ancestor of some other node $V$, for this we can assign a discovery time to each vertex $V$ in the graph $G$ based on the DFS traversal, so that we can know which node was discovered before or after another. e.g. in $G_1$ with the traversal A -> B -> C the dicovery times for each node will be respectively 1, 2, 3; with this we know that A was discovered before C since discovery_time[A] < discovery_time[C].

Now we need to know if some vertex $U$ is an articulation point. So, for that we will check the following conditions:

1. If there is NO way to get to a node $V$ with strictly smaller discovery time than the discovery time of $U$ following the DFS traversal, then $U$ is an articulation point. (it has to be strictly because if it is equal it means that $U$ is the root of a cycle in the DFS traversal which means that $U$ is still an articulation point).

2. If $U$ is the root of the DFS tree and it has at least 2 children subgraphs disconnected from each other, then $U$ is an articulation point.

So, for implementation details, we will think of it as if for every node $U$ we have to find the node $V$ with the least discovery time that can be reached from $U$ following some DFS traversal path which does not require to pass through any already visited nodes, and let's call this node $low$.

Then, we can know that $U$ is an articulation point if the following condition is satisfied: discovery_time[U] <= low[V] ( $V$ in this case represents an adjacent node of $U$ ). To implement this, in each node $V$ we will store some identifier of its corresponding node $low$ found, this identifier will be the corresponding $low's$ discovery time because it helps us to know when the node $low$ was discovered, hence it helps us to know by which node we can discover $U$ first.

### C++ Code

// adj[u] = adjacent nodes of u
// ap = AP = articulation points
// p = parent
// disc[u] = discovery time of u
// low[u] = 'low' node of u

int dfsAP(int u, int p) {
int children = 0;
low[u] = disc[u] = ++Time;
for (int& v : adj[u]) {
if (v == p) continue; // we don't want to go back through the same path.
// if we go back is because we found another way back
if (!disc[v]) { // if V has not been discovered before
children++;
dfsAP(v, u); // recursive DFS call
if (disc[u] <= low[v]) // condition #1
ap[u] = 1;
low[u] = min(low[u], low[v]); // low[v] might be an ancestor of u
} else // if v was already discovered means that we found an ancestor
low[u] = min(low[u], disc[v]); // finds the ancestor with the least discovery time
}
return children;
}

void AP() {
ap = low = disc = vector<int>(adj.size());
Time = 0;
for (int u = 0; u < adj.size(); u++)
if (!disc[u])
ap[u] = dfsAP(u, u) > 1; // condition #2
}


## Bridges

Let's define what a bridge is. We say that an edge $UV$ in a graph $G$ with $C$ connected components is a bridge if its removal increases the number of connected components of $G$. In other words, let $C'$ be number of connected components after removing edge $UV$, if $C' > C$ then the edge $UV$ is a bridge.

The idea for the implementation is exactly the same as for articulation points except for one thing, to say that the edge $UV$ is a bridge, the condition to satisfy is: discovery_time[U] < low[V] instead of discovery_time[U] <= low[V]. Notice that the only change was comparing strictly lesser instead of lesser of equal.

#### But why is this ?

If discovery_time[U] is equal to low[V] it means that there is a path from $V$ that goes back to $U$ ( $V$ in this case represents an adjacent node of $U$ ), or in other words we can just say that we found a cycle rooted in $U$. For articulation points if we remove $U$ from the graph it will increase the number of connected components, but in the case of bridges if we remove the edge $UV$ the number of connected components will remain the same. For bridges we need to be sure that the edge $UV$ is not involved in any cycle. A way to be sure of this is just to check that low[V] is strictly greater than discovery_time[U].

In the graph shown above the edge $AB$ is a bridge because low[B] is strictly greater than disc[A]. The edge $BC$ is not a bridge because low[C] is equal to disc[B].

### C++ Code

// br = bridges, p = parent

vector<pair<int, int>> br;

int dfsBR(int u, int p) {
low[u] = disc[u] = ++Time;
for (int& v : adj[u]) {
if (v == p) continue; // we don't want to go back through the same path.
// if we go back is because we found another way back
if (!disc[v]) { // if V has not been discovered before
dfsBR(v, u);  // recursive DFS call
if (disc[u] < low[v]) // condition to find a bridge
br.push_back({u, v});
low[u] = min(low[u], low[v]); // low[v] might be an ancestor of u
} else // if v was already discovered means that we found an ancestor
low[u] = min(low[u], disc[v]); // finds the ancestor with the least discovery time
}
}

void BR() {
Time = 0;
for (int u = 0; u < adj.size(); u++)
if (!disc[u])
dfsBR(u, u)
}


## FAQ

• Why low[u] = min(low[u], disc[v]) instead of low[u] = min(low[u], low[v]) ?

Let's consider node C in the graph above, in the DFS traversal the nodes after C are: D and E, when the DFS traversal reaches E we find C again, if we take its $low$ time, low[E] will be equal to disc[A] but at this point, when we return back to C in the DFS we will be omitting the fact that $U$ is the root of a cycle (which makes it an articulation point) and we will be saying that there is a path from E to some ancestor of C (in this case A) which does not require C and such path does not exist in the graph, therefore the algorithm will say that C is NOT an articulation point which is totally false since the only way to reach D and E is passing through C.

## Problems

315 Network (Points)

610 Street Directions (Bridges)

10199 Tourist Guide (Points)

10765 Doves and Bombs (Points)

• +76

 » 3 years ago, # |   0 Good explanation, nice draws
 » 3 years ago, # |   0 $+\text{TREE}(\text{G}(64))$ $\text{prro :v}$ $\square$
 » 3 years ago, # |   +3 The best explanation that I found, i've been looking for someone who could explain this subject, and I think I found that guy. +10 and to favorite.
 » 2 years ago, # | ← Rev. 2 →   0 Auto comment: topic has been updated by searleser97
 » 2 years ago, # |   0 can you also explain how to find the biconnected components?
•  » » 2 years ago, # ^ |   0 Sure, I will be elaborating on that on another post.
•  » » » 19 months ago, # ^ |   0 I am still waiting for the explanation of biconnected components
 » 2 years ago, # |   0 Good tutorial with nice explanations and examples
 » 2 years ago, # |   0  for (int u = 0; i < adj.size(); u++) I think there is a little mistake
•  » » 2 years ago, # ^ |   0 Thanks, I will fix it
•  » » » 2 years ago, # ^ |   0 In articulation point code can we write. low[u]=min(low[u],low[v]) instead of low[u]=min(low[u],disc[v])??
•  » » » » 2 years ago, # ^ |   0 No, we can't, you might want to check the last drawing of the post where I give an explanation exactly of what you are asking.
 » 2 years ago, # | ← Rev. 2 →   0 one doubt, help please can i get all the edges which are part of a cycle by changing the condition in bridge code ??
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 You can create an array containing the parents of each of the nodes in the path, however you might be looking for Strongly Connected Components which uses a very similar idea. I recommend you to read about that topic. Now that you understood Tarjan's Idea it will be very straight forward for you to understand Strongly Connected Components
•  » » » 2 years ago, # ^ |   0 yes,i know about that but i guess it's complexity is (exponential) very bad. That is why i am looking for an aternate .Thank you btw
 » 2 years ago, # |   0 How did you make these drawings?They look great.
•  » » 2 years ago, # ^ |   0 I used google drawings :D
 » 2 years ago, # |   0 I really couldn't understand what do you mean by So, for implementation details, we will think of it as if for every node U we have to find the node V with the least discovery time that can be reached from U following some DFS traversal path which does not require to pass through any already visited nodes, and let's call this node low.? To be specific, I didn't understand the meaning of low?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 low will contain the lowest discovery time of each node v, remember that if we find a cycle then all the nodes in such cycle will have the same low discovery time. low[v] will help us to detect whether or not we found a back edge i.e. an edge going back to the same path where we came from.
•  » » » 23 months ago, # ^ |   0 remember that if we find a cycle then all the nodes in such cycle will have the same low discovery time — why it will same? Can you explain this part a bit? Thanks
•  » » » » 23 months ago, # ^ |   0 The condition if (disc[u] <= low[v]) // condition #1 ap[u] = 1; Would pass for 3 nodes cylic graph and will treat the root node as Articulation point (Which is ideally not the Articulation point). Please correct me If I am wrong.
•  » » » » » 23 months ago, # ^ |   0 That is why we handle the root case with condition #2, "If U is the root of the DFS tree and it has at least 2 children subgraphs disconnected from each other, then U is an articulation point." you can see this same condition in the code, it is marked as // condition #2.
•  » » » » 23 months ago, # ^ |   0 I suggest you to do some simulation by hand so you can observe this better. However, a quick explanation would be that whenever we find a visited node, then we update the low of all the nodes in the current path with the same discovery time of the visited node found.
 » 2 years ago, # |   +1 Can we use " low[u] = min(low[u], low[v]) " while finding bridges, I am not able to draw a case where it will not work while finding bridges? Thanks
•  » » 2 years ago, # ^ |   0 I am not able to draw case either. Which makes sense to me since the condition to find a bridge is disc[u] < low[v] and noticing the strict lesser condition, we can observe that in the case of bridges we don't care about the node that is the root of a cycle, which was the case that we should consider for Articulation Points. In conclusion by the informal proof, when finding just bridges you could use low[u] = min(low[u], low[v]), I suggest you to make a more formal proof of this just to be sure.
•  » » » 2 years ago, # ^ |   0 Thanks
 » 2 years ago, # |   0 Good explanation ;_;
 » 23 months ago, # |   0 Does anybody have links to problems based on above approach??It would be very helpful.Thanks in advance.
•  » » 22 months ago, # ^ |   +5 I just added a "problems" section in the post :D
 » 22 months ago, # |   0 the algorithm of ap doesn't work with graph  { {1, 2}, {2, 3}, {3, 1}, }  . if the dfs starts with 1, 1 will be recorded as articulation point. if (disc[u] <= low[v]) needs to be changed to if (u != p && disc[u] <= low[v]) in your implementation to identify u is not the root of dfs tree.
•  » » 21 month(s) ago, # ^ |   0 I just tested the code and it works fine for your test case. No modification needed
 » 18 months ago, # |   0 Nailed it bro, thanks <3
 » 18 months ago, # |   0 Why did low[current_node] = ++time; I mean why did time is assigned to low[current_node] ?
•  » » 17 months ago, # ^ |   0 a way to see it is that Time is helping us to also uniquely identify each of the nodes by their discovery time. So, initially what we are doing is assigning low[u] to be itself u, but later we update low[u] if we find a node that has lower discovery time following DFS traversal. Notice that if we don't find such node then by the definition of low then low[u] must equal disc[u] and hence, the initial assumption will be preserved.
 » 17 months ago, # |   0 Man the representations used are so good and DOPE. Sharing this with my friends.
 » 14 months ago, # |   0 In case where we found an ancestor of the node, why do we minimise the low time of the node with discovery time of ancestor and not low time of ancestor.I mean why not  else // if v was already discovered means that we found an ancestor low[u] = min(low[u], low[v]); 
•  » » 14 months ago, # ^ | ← Rev. 4 →   0 Because if you use the lowest of that ancestor, it can point way too highhttps://pasteboard.co/JTasj2Y.jpgin this example if node 5 uses the lowest in node 3 in which theres a back edge to the root, node 3 will not be detected as an ap because its lowest in its subtree is 1 even though it should just be 3.
•  » » » 14 months ago, # ^ |   +1 Interesting. Thank you very much for this counter example. I appreciate!
 » 13 months ago, # |   0 Question about articulation points.From the code, it seems like failing condition #2 would overwrite condition #1?So what if ap[u] = 1 because this is true: if (disc[u] <= low[v]) // condition #1 ap[u] = 1;But then when you exit out of the dfs, could this be set to 0 because let's say the dfs only returned 1 children? ap[u] = dfsAP(u, u) > 1;I assume that condition 1 could be true when condition 2 isn't (otherwise we would just check for condition 2), so wouldn't this be an issue?
•  » » 10 months ago, # ^ |   0 ap[u] = dfsAP(u,u)>1 ; this condition is only applied on the roots of the components so we don't care if it overwrites condition #1. Cuz anyway for roots we are checking only condition #2.
 » 11 months ago, # |   0 For finding bridges, why isn't it low[u] < low[v]?. My explanation is that, u would receive its low value from v, while back propogating, so any back edges would also be available at low[u]
•  » » 10 months ago, # ^ |   0 if low[v]=low[u] then there is a cycle from u to v so even after removing u-v edge graph won't be disconnected.
 » 10 months ago, # |   +1 The explanation was so good. This guy deserves more upvotes.
 » 10 months ago, # |   0 low[u] = min(low[u], disc[v]);i don't understand this linewhy we can't use low[u]=min(low[u],low[v]);
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 In low we are actually storing the lowest discovery time of vertex that are reachable through vertex u either directly using backedge or some sequence of tree edge and then backedge (or that vertex itself obviously)
•  » » » 10 months ago, # ^ |   0 but low[v] will give me the lowest vertex I can reach from vso if I reach v then I can also reach low[v] and that will be the lowest.
•  » » » » 10 months ago, # ^ |   0 notice I have written "BACKEDGE" and not "BACKEDGES", after you have encounter a backedge you are no longer considering path after that.
 » 3 weeks ago, # |   0 Thanks!!, FAQ section really helped a lot