Articulation Points in Graph in DSA Typescript

Mental Model

An articulation point is a node in a network that, if removed, breaks the network into separate parts.

Analogy: Imagine a city connected by roads. Some intersections are so important that if they close, parts of the city become unreachable from each other.

Graph:
  1
 / \
2 - 3
|
4

Articulation points: 2 because removing 2 disconnects 4 from the rest.

Dry Run Walkthrough

Input: Graph with edges: 1-2, 1-3, 2-3, 2-4

Goal: Find all nodes that, if removed, increase the number of disconnected parts in the graph

Step 1: Start DFS from node 1, set discovery time and low value to 1

discovery: {1:1}, low: {1:1}, visited: {1}, parent: {1:null}

Why: We begin exploring the graph from node 1 to find articulation points

Step 2: Visit node 2 from node 1, set discovery and low to 2

discovery: {1:1, 2:2}, low: {1:1, 2:2}, visited: {1,2}, parent: {1:null, 2:1}

Why: We explore neighbors to find back edges and update low values

Step 3: Visit node 3 from node 2, set discovery and low to 3

discovery: {1:1, 2:2, 3:3}, low: {1:1, 2:2, 3:3}, visited: {1,2,3}, parent: {1:null, 2:1, 3:2}

Why: Continue DFS to explore all nodes

Step 4: Node 3 has neighbor 1 which is visited and not parent, update low[3] to min(low[3], discovery[1]) = 1

low: {1:1, 2:2, 3:1}

Why: Back edge found from 3 to 1, update low to reflect earliest reachable ancestor

Step 5: Backtrack to node 2, update low[2] to min(low[2], low[3]) = 1

low: {1:1, 2:1, 3:1}

Why: Low value of child affects parent's low value

Step 6: Visit node 4 from node 2, set discovery and low to 4

discovery: {1:1, 2:2, 3:3, 4:4}, low: {1:1, 2:1, 3:1, 4:4}, visited: {1,2,3,4}, parent: {1:null, 2:1, 3:2, 4:2}

Why: Explore all nodes to find articulation points

Step 7: Node 4 has no unvisited neighbors, backtrack to 2 and update low[2] to min(low[2], low[4]) = 1

low: {1:1, 2:1, 3:1, 4:4}

Why: Update low values after exploring child

Step 8: Check articulation point condition at node 2: low[4] >= discovery[2] (4 >= 2), so node 2 is articulation point

Articulation points: {2}

Why: If child's low is not less than parent's discovery, parent is articulation point

Result:

Articulation points: 2
Graph state unchanged

Annotated Code

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]>;
  time: number;
  constructor() {
    this.adjacencyList = new Map();
    this.time = 0;
  }

  addEdge(u: number, v: number) {
    if (!this.adjacencyList.has(u)) this.adjacencyList.set(u, []);
    if (!this.adjacencyList.has(v)) this.adjacencyList.set(v, []);
    this.adjacencyList.get(u)!.push(v);
    this.adjacencyList.get(v)!.push(u);
  }

  findArticulationPoints(): number[] {
    const visited = new Map<number, boolean>();
    const disc = new Map<number, number>();
    const low = new Map<number, number>();
    const parent = new Map<number, number | null>();
    const ap = new Set<number>();

    const dfs = (u: number) => {
      visited.set(u, true);
      this.time++;
      disc.set(u, this.time); // discovery time
      low.set(u, this.time);  // low value
      let children = 0;

      for (const v of this.adjacencyList.get(u) || []) {
        if (!visited.get(v)) {
          children++;
          parent.set(v, u);
          dfs(v);
          low.set(u, Math.min(low.get(u)!, low.get(v)!)); // update low[u]

          // If u is root and has two or more children
          if (parent.get(u) === null && children > 1) {
            ap.add(u);
          }

          // If u is not root and low[v] >= disc[u]
          if (parent.get(u) !== null && low.get(v)! >= disc.get(u)!) {
            ap.add(u);
          }
        } else if (v !== parent.get(u)) {
          low.set(u, Math.min(low.get(u)!, disc.get(v)!)); // back edge
        }
      }
    };

    for (const node of this.adjacencyList.keys()) {
      if (!visited.get(node)) {
        parent.set(node, null);
        dfs(node);
      }
    }

    return Array.from(ap).sort((a, b) => a - b);
  }
}

// Driver code
const graph = new Graph();
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(2, 4);

const articulationPoints = graph.findArticulationPoints();
console.log("Articulation points:", articulationPoints.join(", "));

visited.set(u, true); this.time++; disc.set(u, this.time); low.set(u, this.time);

Mark node u visited and set discovery and low times

for (const v of this.adjacencyList.get(u) || []) {

Traverse all neighbors of u

if (!visited.get(v)) {

If neighbor v not visited, explore it

children++; parent.set(v, u); dfs(v);

Count children and recurse DFS on v

low.set(u, Math.min(low.get(u)!, low.get(v)!));

Update low[u] based on child's low[v]

if (parent.get(u) === null && children > 1) { ap.add(u); }

Root node with multiple children is articulation point

if (parent.get(u) !== null && low.get(v)! >= disc.get(u)!) { ap.add(u); }

Non-root node where child's low >= discovery is articulation point

} else if (v !== parent.get(u)) { low.set(u, Math.min(low.get(u)!, disc.get(v)!)); }

Update low[u] for back edge to ancestor

Output

Articulation points: 2

Complexity Analysis

Time: O(V + E) because we visit each node and edge once during DFS

Space: O(V) for storing discovery, low, parent, visited, and recursion stack

vs Alternative: Naive approach checks connectivity after removing each node, costing O(V*(V+E)), much slower than DFS-based O(V+E)

Edge Cases

Graph with no edges

No articulation points because no node removal disconnects graph

DSA Typescript

if (!visited.get(node)) { parent.set(node, null); dfs(node); }

Graph with single node

No articulation points because removing the only node leaves empty graph

DSA Typescript

if (!visited.get(node)) { parent.set(node, null); dfs(node); }

Graph with multiple disconnected components

Algorithm runs DFS on each component separately and finds articulation points in each

DSA Typescript

for (const node of this.adjacencyList.keys()) { if (!visited.get(node)) { parent.set(node, null); dfs(node); } }

When to Use This Pattern

When a problem asks for nodes whose removal breaks connectivity, use articulation points detection with DFS and low-link values.

Common Mistakes

Mistake: Not handling root node separately for articulation point condition
Fix: Check if root has more than one child to mark it as articulation point

Mistake: Updating low value incorrectly by not considering back edges
Fix: Update low[u] with discovery time of visited neighbors that are not parent

Summary

Find nodes in a graph that disconnect it if removed.

Use when you want to identify critical points in networks or connectivity.

Use DFS with discovery and low times to detect articulation points efficiently.

Practice

1. What is an articulation point (or cut vertex) in a graph?

easy

A. A vertex that, when removed, increases the number of connected components

B. A vertex with the highest degree in the graph

C. A vertex connected to all other vertices

D. A vertex that has no edges connected to it

Solution

1. Step 1: Understand the definition of articulation point

   An articulation point is a vertex that, if removed, breaks the graph into more pieces (connected components).

2. Step 2: Compare options with definition

   Only A vertex that, when removed, increases the number of connected components matches this definition exactly.

3. Final Answer:

   A vertex that, when removed, increases the number of connected components -> Option A

4. Quick Check:

   Articulation point = vertex increasing components when removed [OK]

Hint: Articulation point breaks graph connectivity when removed [OK]

Common Mistakes:

• Confusing articulation point with highest degree vertex
• Thinking articulation point connects to all vertices
• Assuming isolated vertex is articulation point

2. Which of the following is the correct TypeScript function signature to find articulation points in an undirected graph represented as adjacency list?

easy

A. function findArticulationPoints(graph: number): number[]

B. function findArticulationPoints(graph: number[][]): void

C. function findArticulationPoints(graph: string): number[]

D. function findArticulationPoints(graph: Map): number[]

Solution

1. Step 1: Identify the graph representation type

   An adjacency list is best represented as a Map from node number to array of connected nodes.

2. Step 2: Check function signature compatibility

   function findArticulationPoints(graph: Map): number[] uses Map and returns number[] which fits the problem.

3. Final Answer:

   function findArticulationPoints(graph: Map<number, number[]>): number[] -> Option D

4. Quick Check:

   Adjacency list as Map with number arrays returns number array [OK]

Hint: Use Map for adjacency list in TypeScript [OK]

Common Mistakes:

• Using string type for graph input
• Returning void instead of list of articulation points
• Passing graph as a single number

3. Given the following TypeScript code snippet to find articulation points, what will be the output for the graph edges: [[0,1],[1,2],[2,0],[1,3]]?

const graph = new Map();
graph.set(0, [1, 2]);
graph.set(1, [0, 2, 3]);
graph.set(2, [0, 1]);
graph.set(3, [1]);

const articulationPoints = findArticulationPoints(graph);
console.log(articulationPoints);

medium

A. [0, 1]

B. [3]

C. [1]

D. []

Solution

1. Step 1: Analyze the graph structure

   The graph has a triangle between 0,1,2 and a leaf node 3 connected to 1.

2. Step 2: Identify articulation points

   Removing node 1 disconnects node 3 from the rest, so 1 is an articulation point. Nodes 0 and 2 are part of a cycle, so not articulation points. Node 3 is a leaf, not articulation point.

3. Final Answer:

   [1] -> Option C

4. Quick Check:

   Only node 1 disconnects graph when removed [OK]

Hint: Check if removing node splits graph into more parts [OK]

Common Mistakes:

• Thinking nodes in cycle are articulation points
• Including leaf nodes as articulation points
• Ignoring connectivity after removal

4. The following TypeScript code attempts to find articulation points but has a bug. What is the bug?

function dfs(u: number, parent: number) {
  visited[u] = true;
  disc[u] = time;
  low[u] = time;
  time++;
  let children = 0;
  for (const v of graph.get(u) || []) {
    if (!visited[v]) {
      children++;
      dfs(v, u);
      low[u] = Math.min(low[u], low[v]);
      if (parent !== -1 && low[v] >= disc[u]) {
        articulationPoints.add(u);
      }
    } else if (v !== parent) {
      low[u] = Math.min(low[u], disc[v]);
    }
  }
  if (parent === -1 && children > 1) {
    articulationPoints.add(u);
  }
}

medium

A. The 'visited' array is not initialized before DFS

B. The root node condition for articulation point is checked after the loop

C. The variable 'time' is not incremented correctly

D. The condition 'low[v] >= disc[u]' should be 'low[v] > disc[u]'

Solution

1. Step 1: Review DFS variables initialization

   The code uses 'visited' array but does not show its initialization before DFS calls.

2. Step 2: Identify missing initialization impact

   If 'visited' is not initialized to false for all nodes, DFS may skip nodes or behave incorrectly.

3. Final Answer:

   The 'visited' array is not initialized before DFS -> Option A

4. Quick Check:

   Uninitialized visited array causes DFS errors [OK]

Hint: Always initialize visited array before DFS traversal [OK]

Common Mistakes:

• Assuming time increments incorrectly
• Misunderstanding root node articulation condition
• Changing condition from >= to > incorrectly

5. You have a network of computers represented as an undirected graph. You want to find all critical computers whose failure would split the network. The graph has 7 nodes with edges: [[0,1],[1,2],[2,0],[1,3],[3,4],[4,5],[5,3],[4,6]]. Which nodes are articulation points?

hard

A. [0, 2, 5]

B. [1, 3, 4]

C. [3, 5, 6]

D. [1, 4, 6]

Solution

1. Step 1: Analyze graph components and cycles

   Nodes 0,1,2 form a triangle (cycle). Nodes 3,4,5 form another cycle. Node 6 is connected only to 4.

2. Step 2: Identify articulation points

   Removing 1 disconnects node 3 and its cycle from 0,2. Removing 3 disconnects 4,5,6 from 1. Removing 4 disconnects node 6 from rest. So articulation points are 1, 3, and 4.

3. Final Answer:

   [1, 3, 4] -> Option B

4. Quick Check:

   Nodes connecting cycles and leaf nodes are articulation points [OK]

Hint: Look for nodes connecting cycles or leaf nodes [OK]

Common Mistakes:

• Including nodes inside cycles as articulation points
• Missing nodes connecting leaf nodes
• Confusing leaf nodes as articulation points