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.