### searleser97's blog

By searleser97, 13 months 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

 » 13 months ago, # |   0 Good explanation, nice draws
 » 13 months ago, # |   0 $+\text{TREE}(\text{G}(64))$ $\text{prro :v}$ $\square$
 » 13 months 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.
 » 8 months ago, # | ← Rev. 2 →   0 Auto comment: topic has been updated by searleser97
 » 8 months ago, # |   0 can you also explain how to find the biconnected components?
•  » » 8 months ago, # ^ |   0 Sure, I will be elaborating on that on another post.
•  » » » 5 weeks ago, # ^ |   0 I am still waiting for the explanation of biconnected components
 » 8 months ago, # |   0 Good tutorial with nice explanations and examples
 » 8 months ago, # |   0  for (int u = 0; i < adj.size(); u++) I think there is a little mistake
•  » » 8 months ago, # ^ |   0 Thanks, I will fix it
•  » » » 6 months 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])??
•  » » » » 6 months 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.
 » 8 months 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 ??
•  » » 8 months 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
•  » » » 8 months 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
 » 8 months ago, # |   0 How did you make these drawings?They look great.
•  » » 8 months ago, # ^ |   0 I used google drawings :D
 » 8 months 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?
•  » » 8 months 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.
•  » » » 5 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
•  » » » » 5 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.
•  » » » » » 5 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.
•  » » » » 5 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.
 » 8 months 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
•  » » 8 months 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.
•  » » » 8 months ago, # ^ |   0 Thanks
 » 7 months ago, # |   0 Good explanation ;_;
 » 5 months ago, # |   0 Does anybody have links to problems based on above approach??It would be very helpful.Thanks in advance.
•  » » 4 months ago, # ^ |   +5 I just added a "problems" section in the post :D
 » 4 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.
•  » » 3 months ago, # ^ |   0 I just tested the code and it works fine for your test case. No modification needed