Articulation Points in Graph in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of articulation points detection on a simple graph

Given the following TypeScript code that finds articulation points in an undirected graph, what is the output printed by the program?

DSA Typescript

class Graph {
  vertices: number;
  adjacencyList: Map<number, number[]>;

  constructor(vertices: number) {
    this.vertices = vertices;
    this.adjacencyList = new Map();
    for (let i = 0; i < vertices; i++) {
      this.adjacencyList.set(i, []);
    }
  }

  addEdge(u: number, v: number): void {
    this.adjacencyList.get(u)?.push(v);
    this.adjacencyList.get(v)?.push(u);
  }

  articulationPoints(): number[] {
    const visited = new Array(this.vertices).fill(false);
    const disc = new Array(this.vertices).fill(-1);
    const low = new Array(this.vertices).fill(-1);
    const parent = new Array(this.vertices).fill(-1);
    const ap = new Array(this.vertices).fill(false);
    let time = 0;

    const dfs = (u: number) => {
      visited[u] = true;
      disc[u] = low[u] = time++;
      let children = 0;

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

          if (parent[u] === -1 && children > 1) {
            ap[u] = true;
          }

          if (parent[u] !== -1 && low[v] >= disc[u]) {
            ap[u] = true;
          }
        } else if (v !== parent[u]) {
          low[u] = Math.min(low[u], disc[v]);
        }
      }
    };

    for (let i = 0; i < this.vertices; i++) {
      if (!visited[i]) dfs(i);
    }

    const result: number[] = [];
    for (let i = 0; i < this.vertices; i++) {
      if (ap[i]) result.push(i);
    }
    return result;
  }
}

const g = new Graph(5);
g.addEdge(1, 0);
g.addEdge(0, 2);
g.addEdge(2, 1);
g.addEdge(0, 3);
g.addEdge(3, 4);

console.log(g.articulationPoints());

A [0, 3]

B [1, 3]

C [0, 2, 3]

D [3, 4]

💡 Hint

Think about nodes whose removal increases the number of connected components.

The graph has 5 nodes with edges forming a triangle between 0,1,2 and a chain 0-3-4. Node 0 connects the triangle to the chain, so removing 0 disconnects the graph. Node 3 connects node 4 to the rest, so removing 3 disconnects node 4. Thus articulation points are 0 and 3.

🧠 Conceptual

intermediate

Understanding articulation points in a graph

Which of the following best describes an articulation point in an undirected graph?

A A vertex that is connected to all other vertices directly.

B A vertex with the highest degree in the graph.

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

D A vertex that has no edges connected to it.

💡 Hint

Think about the effect of removing a vertex on graph connectivity.

An articulation point is a vertex whose removal disconnects the graph or increases the number of connected components.

🔧 Debug

advanced

Identify the error in articulation points detection code

Consider this TypeScript snippet for articulation points detection. What error will it cause when run?

DSA Typescript

function findAP(graph: Map<number, number[]>, vertices: number): number[] {
  const visited = new Array(vertices).fill(false);
  const disc = new Array(vertices).fill(-1);
  const low = new Array(vertices).fill(-1);
  const parent = new Array(vertices).fill(-1);
  const ap = new Array(vertices).fill(false);
  let time = 0;

  function dfs(u: number) {
    visited[u] = true;
    disc[u] = low[u] = time++;
    let children = 0;

    for (const v of graph.get(u) || []) {
      if (!visited[v]) {
        children++;
        parent[v] = u;
        dfs(v);
        low[u] = Math.min(low[u], low[v]);

        if (parent[u] === -1 && children > 1) ap[u] = true;
        if (parent[u] !== -1 && low[v] >= disc[u]) ap[u] = true;
      } else if (v !== parent[u]) {
        low[u] = Math.min(low[u], disc[v]);
      }
    }
  }

  for (let i = 0; i < vertices; i++) {
    if (!visited[i]) dfs(i);
  }

  const result: number[] = [];
  for (let i = 0; i < vertices; i++) {
    if (ap[i]) result.push(i);
  }
  return result;
}

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

console.log(findAP(g, 4));

A Output: []

B SyntaxError: Unexpected token

C Output: [0]

D TypeError: Cannot read property 'Symbol.iterator' of undefined

💡 Hint

Check how adjacency lists are accessed in the for loop.

The code calls graph.get(u) without checking if it returns undefined. For node 1 and 2, adjacency lists exist, but if a node has no edges, graph.get(u) returns undefined, causing a TypeError when iterated.

❓ Predict Output

advanced

Output of articulation points in a disconnected graph

What is the output of the following TypeScript code that finds articulation points in a disconnected graph?

DSA Typescript

class Graph {
  vertices: number;
  adjacencyList: Map<number, number[]>;

  constructor(vertices: number) {
    this.vertices = vertices;
    this.adjacencyList = new Map();
    for (let i = 0; i < vertices; i++) {
      this.adjacencyList.set(i, []);
    }
  }

  addEdge(u: number, v: number): void {
    this.adjacencyList.get(u)?.push(v);
    this.adjacencyList.get(v)?.push(u);
  }

  articulationPoints(): number[] {
    const visited = new Array(this.vertices).fill(false);
    const disc = new Array(this.vertices).fill(-1);
    const low = new Array(this.vertices).fill(-1);
    const parent = new Array(this.vertices).fill(-1);
    const ap = new Array(this.vertices).fill(false);
    let time = 0;

    const dfs = (u: number) => {
      visited[u] = true;
      disc[u] = low[u] = time++;
      let children = 0;

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

          if (parent[u] === -1 && children > 1) {
            ap[u] = true;
          }

          if (parent[u] !== -1 && low[v] >= disc[u]) {
            ap[u] = true;
          }
        } else if (v !== parent[u]) {
          low[u] = Math.min(low[u], disc[v]);
        }
      }
    };

    for (let i = 0; i < this.vertices; i++) {
      if (!visited[i]) dfs(i);
    }

    const result: number[] = [];
    for (let i = 0; i < this.vertices; i++) {
      if (ap[i]) result.push(i);
    }
    return result;
  }
}

const g = new Graph(7);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(1, 3);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.addEdge(5, 3);
// Node 6 is disconnected

console.log(g.articulationPoints());

A [1, 3]

B [0, 1, 3]

C [3, 4]

D [6]

💡 Hint

Consider articulation points in each connected component separately.

The graph has two components: a triangle 0-1-2 with a bridge at 1 to the second component 3-4-5 cycle. Node 1 connects the triangle to the rest, so it is an articulation point. Node 3 connects nodes 4 and 5 to node 1, so it is also an articulation point. Node 6 is isolated and not an articulation point.

🚀 Application

expert

Number of articulation points in a complex graph

Given a graph with 8 vertices and edges: (0-1), (1-2), (2-0), (1-3), (3-4), (4-5), (5-3), (5-6), (6-7), how many articulation points does this graph have?

A 2

B 3

C 4

D 5

💡 Hint

Identify vertices whose removal disconnects parts of the graph.

The graph has a triangle (0,1,2), connected to a cycle (3,4,5) via node 1. Node 5 connects to a chain (6-7). Articulation points are 1 (connects triangle to rest), 3 (connects cycle to chain), and 5 (connects chain end). So total 3 articulation points.

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