AIOJ

Articulation Points

For an undirected graph, if deleting a vertex increases the number of maximal connected components of the graph, that vertex is an articulation point (also called a cut vertex).

Process

If we try to delete each vertex and check whether the graph remains connected, the complexity is very high. We therefore introduce a common algorithm: Tarjan's algorithm.

First, consider the following graph:

It is easy to see that vertex 2 is an articulation point, and that it is the only one in this graph.

First, assign timestamps according to DFS order (the order of visitation).

We store this information in an array called dfn.

We also need another array, low, which stores the smallest timestamp reachable without passing through the vertex's parent.

For example, low[2] is 1, while low[5] and low[6] are 3.

We then begin DFS. The criterion for determining whether a vertex is an articulation point is: for a vertex $u$ , if there is at least one vertex $v$ (a child of $u$ ) such that $low_v \geq dfn_u$ , meaning that it cannot return to an ancestor, then $u$ is an articulation point.

This criterion does not apply to the starting point of the search, which requires special handling. If the starting point is not an articulation point, every other vertex can also be reached by another path, so the starting point “searched downward only once”; that is, it has only one child in the search tree. If it has two or more children in the search tree, it must be an articulation point (for example, if the graph above were searched from 2, the search tree would have two children: 3 or 4, and 5 or 6). If it has only one child, deleting it has no effect. In the graph below, for example, a cycle is formed.

When visiting the child of 1, suppose DFS first goes to 2, marks it as visited, then recursively continues to 4, and from 4 to 3. When the recursion backtracks, it finds that 3 has already been visited, so the vertex is not an articulation point.

The pseudocode for updating low is:

\begin{array}{ll} 1 & \textbf{if } v \text{ is a son of } u \\ 2 & \qquad \text{low}_u = \min(\text{low}_u, \text{low}_v) \\ 3 & \textbf{else} \\ 4 & \qquad \text{low}_u = \min(\text{low}_u, \text{dfn}_v) \\ \end{array}

Examples

Luogu P3388 (Template) Articulation Point (Cut Vertex)

Example Code

/*
Luogu P3388 [Template] Articulation Point (Cut Vertex)
*/
#include <iostream>
#include <vector>
using namespace std;
int n, m;  // n: number of vertices, m: number of edges
int dfn[100001], low[100001], idx, res;
// dfn: records the timestamp of each vertex
// low: smallest vertex number reachable without passing through the parent; idx: timestamp; res: number of answers
bool vis[100001], flag[100001];  // flag: answer; vis: marks whether a vertex has been visited
vector<int> edge[100001];        // graph storage

void Tarjan(int u, int fa) {  // u: current vertex number; fa: its parent's number
  vis[u] = true;              // mark as visited
  low[u] = dfn[u] = ++idx;    // assign a timestamp
  int child = 0;              // number of children of this vertex
  for (const auto &v : edge[u]) {  // visit every neighbor of this vertex (C++11)
    if (!vis[v]) {
      child++;                       // one more child
      Tarjan(v, u);                  // continue
      low[u] = min(low[u], low[v]);  // update the smallest reachable vertex number
      if (fa != u && low[v] >= dfn[u] && !flag[u]) {  // main logic
        // If this is not the root, the smallest point reachable without going through the parent
        // meets the articulation-point condition, and this vertex has not been marked; deleting the parent disconnects it
        flag[u] = true;
        res++;  // record the answer
      }
    } else if (v != fa) {
      // If this vertex is not the parent, update the smallest reachable vertex number
      low[u] = min(low[u], dfn[v]);
    }
  }
  // Main logic: the root needs at least two children
  if (fa == u && child >= 2 && !flag[u]) {
    flag[u] = true;
    res++;  // record the answer
  }
}

int main() {
  cin >> n >> m;                  // read the input
  for (int i = 1; i <= m; i++) {  // note that vertices start at 1
    int x, y;
    cin >> x >> y;
    edge[x].push_back(y);
    edge[y].push_back(x);
  }  // use vector to store the graph
  for (int i = 1; i <= n; i++)  // Tarjan's graph need not be connected
    if (!vis[i]) {
      idx = 0;       // initial timestamp is 0
      Tarjan(i, i);  // start from vertex i, whose parent is itself
    }
  cout << res << endl;
  for (int i = 1; i <= n; i++)
    if (flag[i]) cout << i << " ";  // output the result
  return 0;
}

Bridges (Without Multiple Edges)

This is similar to articulation points and is called a bridge.

For an undirected graph, if deleting an edge increases the number of connected components, that edge is called a bridge or cut edge. More rigorously, suppose $G=\{V,E\}$ is a connected graph and $e$ is an edge of it (that is, $e \in E$ ). If $G-e$ is disconnected, then $e$ is a cut edge (bridge) of $G$ .

For example, in the figure below,

Bridge example

the red edge is the cut edge.

Process

This is similar to the articulation-point case; only one change is needed: use $low_v>dfn_u$ , and there is no need to handle the root separately.

Whether an edge is a bridge has nothing to do with whether its endpoint is the root. When finding articulation points, we say that vertex $v$ cannot return to an ancestor (including its parent) without passing through its parent $u$ , so $u$ is an articulation point. If $low_v=dfn_u$ , it can still return to the parent; if vertex $v$ cannot return to an ancestor and has no other route back to its parent, then edge $u-v$ is a bridge.

Implementation

The following code finds bridges in an undirected graph without multiple edges. When isbridge[x] is true, (father[x],x) is a bridge.

C++

int low[MAXN], dfn[MAXN], idx;
bool isbridge[MAXN];
vector<int> G[MAXN];
int cnt_bridge;
int father[MAXN];

void tarjan(int u, int fa) {
  father[u] = fa;
  low[u] = dfn[u] = ++idx;
  for (const auto &v : G[u]) {
    if (!dfn[v]) {
      tarjan(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > dfn[u]) {
        isbridge[v] = true;
        ++cnt_bridge;
      }
    } else if (v != fa) {
      low[u] = min(low[u], dfn[v]);
    }
  }
}

Python

low = [0] * MAXN
dfn = [0] * MAXN
idx = 0
isbridge = [False] * MAXN
G = [[0 for i in range(MAXN)] for j in range(MAXN)]
cnt_bridge = 0
father = [0] * MAXN

def tarjan(u, fa):
    father[u] = fa
    idx = idx + 1
    low[u] = dfn[u] = idx
    for i in range(0, len(G[u])):
        v = G[u][i]
        if dfn[v] == False:
            tarjan(v, u)
            low[u] = min(low[u], low[v])
            if low[v] > dfn[u]:
                isbridge[v] = True
                cnt_bridge = cnt_bridge + 1
        elif v != fa:
            low[u] = min(low[u], dfn[v])

Bridges (With Multiple Edges)

However, the method above has a problem on undirected graphs with multiple edges.

When two vertices may be joined by more than one edge, neither of those edges is a bridge.

Process

One approach is to change the parameter fa to the ID of the edge just traversed (with the same ID for each copy of an edge). In other words, change “do not update through the parent” to “do not update through the edge used to arrive”.

Another, simpler approach is to maintain a flag indicating whether an edge to the parent has already been encountered; after it is marked, update normally when the parent is encountered again.

The following code finds bridges in an undirected graph that may contain multiple edges.

C++

int low[MAXN], dfn[MAXN], idx;
bool isbridge[MAXN];
vector<int> G[MAXN];
int cnt_bridge;
int father[MAXN];

void tarjan(int u, int fa) {
  bool flag = false;
  father[u] = fa;
  low[u] = dfn[u] = ++idx;
  for (const auto &v : G[u]) {
    if (!dfn[v]) {
      tarjan(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > dfn[u]) {
        isbridge[v] = true;
        ++cnt_bridge;
      }
    } else {
      if (v != fa || flag)
        low[u] = min(low[u], dfn[v]);
      else
        flag = true;
    }
  }
}

Exercises

Tarjan's algorithm has many other uses, including finding strongly connected components, contracting components, and solving 2-SAT.

Articulation Points and Bridges

Articulation Points

Process

Examples

Bridges (Without Multiple Edges)

Process

Implementation

Bridges (With Multiple Edges)

Process

Exercises