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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of articulation points detection on a simple graph

What is the output of the following JavaScript code that finds articulation points in the given graph?

DSA Javascript

function findArticulationPoints(graph) {
  const n = graph.length;
  const visited = new Array(n).fill(false);
  const disc = new Array(n).fill(-1);
  const low = new Array(n).fill(-1);
  const parent = new Array(n).fill(-1);
  const ap = new Array(n).fill(false);
  let time = 0;

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

    for (const v of graph[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 < n; i++) {
    if (!visited[i]) dfs(i);
  }

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

const graph = [
  [1, 2],    // 0
  [0, 2],    // 1
  [0, 1, 3, 5], // 2
  [2, 4],    // 3
  [3],       // 4
  [2, 6, 7], // 5
  [5, 7],    // 6
  [5, 6]     // 7
];

console.log(findArticulationPoints(graph));

A [0, 2, 5]

B [2, 3, 5]

C [2, 5]

D [1, 2, 5]

💡 Hint

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

The code uses DFS to find articulation points. Node 2 connects two parts of the graph, and node 5 connects another part. Removing either increases disconnected parts. Other nodes do not satisfy the articulation point conditions.

🧠 Conceptual

intermediate

Understanding articulation points in a graph

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

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

B A vertex with the highest degree in the graph.

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

D A vertex that lies on a cycle in the graph.

💡 Hint

Think about what happens to connectivity when a vertex is removed.

An articulation point is a vertex that, if removed, breaks the graph into more pieces, increasing the number of connected components.

🔧 Debug

advanced

Identify the error in articulation points detection code

What error will the following code produce when run on a graph with cycles?

DSA Javascript

function findAP(graph) {
  const n = graph.length;
  const visited = new Array(n).fill(false);
  const disc = new Array(n).fill(-1);
  const low = new Array(n).fill(-1);
  const parent = new Array(n).fill(-1);
  const ap = new Array(n).fill(false);
  let time = 0;

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

    for (const v of graph[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 < n; i++) {
    if (!visited[i]) dfs(i);
  }

  return ap;
}

A It will produce correct articulation points array with true/false values.

B It will throw a ReferenceError due to undefined variable 'time'.

C It will cause infinite recursion due to missing visited check.

D It will miss some articulation points because of incorrect comparison operator in condition.

💡 Hint

Check the condition that marks articulation points for non-root nodes.

The condition low[v] > disc[u] should be low[v] >= disc[u] to correctly identify articulation points when low[v] equals disc[u]. Using '>' misses some points.

🚀 Application

advanced

Number of articulation points in a complex graph

Given the graph below represented as adjacency list, how many articulation points does it have?

DSA Javascript

const graph = [
  [1, 2],    // 0
  [0, 2, 3], // 1
  [0, 1, 4], // 2
  [1, 5],    // 3
  [2],       // 4
  [3, 6, 7], // 5
  [5, 7],    // 6
  [5, 6, 8], // 7
  [7]        // 8
];

A 4

B 3

C 2

D 5

💡 Hint

Identify nodes whose removal disconnects parts of the graph.

Articulation points are nodes 1, 3, and 5. Removing any of these increases disconnected parts. Other nodes do not disconnect the graph.

❓ Predict Output

expert

Output of articulation points detection on disconnected graph

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

DSA Javascript

function articulationPoints(graph) {
  const n = graph.length;
  const visited = new Array(n).fill(false);
  const disc = new Array(n).fill(-1);
  const low = new Array(n).fill(-1);
  const parent = new Array(n).fill(-1);
  const ap = new Array(n).fill(false);
  let time = 0;

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

    for (const v of graph[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 < n; i++) {
    if (!visited[i]) dfs(i);
  }

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

const graph = [
  [1],       // 0
  [0, 2],    // 1
  [1],       // 2
  [4],       // 3
  [3, 5],    // 4
  [4]        // 5
];

console.log(articulationPoints(graph));

A [1, 4]

B [1, 3, 4]

C [0, 1, 4]

D [1]

💡 Hint

Check articulation points in each disconnected component separately.

The graph has two disconnected parts: nodes 0-1-2 and nodes 3-4-5. Node 1 connects 0 and 2, so it's an articulation point. Node 4 connects 3 and 5, so it's also an articulation point.

Practice

1. What is an articulation point 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, increases the number of disconnected parts in the graph.

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 is always connected to all vertices
• Assuming isolated vertices are articulation points

2. Which of the following is the correct way to initialize a graph adjacency list in JavaScript for articulation point detection?

easy

A. const graph = Array.from({ length: n }, () => []);

B. const graph = new Array(n).fill([]);

C. const graph = Array(n).fill(null);

D. const graph = new Map();

Solution

1. Step 1: Understand adjacency list initialization

   We need an array of separate empty arrays for each vertex to store neighbors.

2. Step 2: Analyze options

   const graph = new Array(n).fill([]); uses fill([]), which fills all positions with the same array reference (wrong). const graph = Array.from({ length: n }, () => []); uses Array.from with a function returning new arrays, so each vertex has its own array (correct). const graph = Array(n).fill(null); fills with null, not arrays. const graph = new Map(); uses Map, which is valid but not the typical adjacency list array.

3. Final Answer:

   const graph = Array.from({ length: n }, () => []); -> Option A

4. Quick Check:

   Separate arrays per vertex = const graph = Array.from({ length: n }, () => []); [OK]

Hint: Use Array.from with function to create separate arrays [OK]

Common Mistakes:

• Using fill([]) creates shared references causing bugs
• Initializing with null instead of arrays
• Confusing Map with adjacency list array

3. Consider the following JavaScript code snippet for finding articulation points in a graph with 4 vertices (0 to 3):

const graph = [[1,2],[0],[0,3],[2]];
const visited = [false, false, false, false];
const disc = [0, 0, 0, 0];
const low = [0, 0, 0, 0];
const parent = [-1, -1, -1, -1];
const ap = [false, false, false, false];
let time = 0;

function dfs(u) {
  visited[u] = true;
  disc[u] = low[u] = ++time;
  let children = 0;
  for (const v of graph[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]);
    }
  }
}

dfs(0);
console.log(ap);

What will be the output printed?

medium

A. [false, false, false, false]

B. [true, false, true, false]

C. [true, true, false, false]

D. [false, true, true, false]

Solution

1. Step 1: Trace DFS and articulation point logic

   Start DFS at 0: children are 1 and 2. For root (0), if children > 1, ap[0] = true. So 0 is articulation point. For vertex 2, low[3] >= disc[2] triggers ap[2] = true.

2. Step 2: Determine articulation points array

   Vertices 0 and 2 are articulation points, others are not. So ap = [true, false, true, false].

3. Final Answer:

   [true, false, true, false] -> Option B

4. Quick Check:

   Root with >1 child and low[v]>=disc[u] mark articulation points [OK]

Hint: Root with multiple children and low[v]>=disc[u] mark articulation points [OK]

Common Mistakes:

• Ignoring root special case with multiple children
• Confusing low and disc arrays
• Not updating low[u] on back edges

4. The following code attempts to find articulation points but has a bug:

function dfs(u) {
  visited[u] = true;
  disc[u] = low[u] = ++time;
  let children = 0;
  for (const v of graph[u]) {
    if (!visited[v]) {
      children++;
      parent[v] = u;
      dfs(v);
      low[u] = Math.min(low[u], low[v]);
      if (low[v] >= disc[u]) ap[u] = true;
    } else if (v !== parent[u]) {
      low[u] = Math.min(low[u], disc[v]);
    }
  }
}

What is the bug in this code?

medium

A. It does not mark visited vertices

B. It uses '>' instead of '>=' in the articulation point check

C. It does not update parent array correctly

D. It misses the root vertex articulation point condition

Solution

1. Step 1: Analyze articulation point conditions

   The code checks if low[v] >= disc[u] to mark articulation points but misses the special case for root vertex which requires children > 1.

2. Step 2: Identify missing root condition

   Without checking if u is root and has multiple children, root articulation points won't be detected.

3. Final Answer:

   It misses the root vertex articulation point condition -> Option D

4. Quick Check:

   Root articulation point requires separate children > 1 check [OK]

Hint: Always check root vertex children count separately [OK]

Common Mistakes:

• Forgetting root vertex special case
• Using wrong comparison operator in articulation check
• Not updating parent array before DFS call

5. Given a connected undirected graph with 5 vertices and edges: 0-1, 1-2, 2-0, 1-3, 3-4, which vertices are articulation points?

hard

A. [1]

B. [0, 1, 3]

C. [1, 3]

D. [3, 4]

Solution

1. Step 1: Visualize the graph and connections

   Vertices 0,1,2 form a triangle. Vertex 1 connects to 3, which connects to 4.

2. Step 2: Identify articulation points

   Removing 1 disconnects 3 and 4 from the rest, so 1 is articulation point. Removing 3 disconnects 4, so 3 is articulation point. 0,2,4 are not articulation points.

3. Final Answer:

   [1, 3] -> Option C

4. Quick Check:

   Vertices connecting subgraphs are articulation points [OK]

Hint: Articulation points connect separate graph parts [OK]

Common Mistakes:

• Including vertices inside cycles as articulation points
• Missing leaf node articulation points
• Confusing articulation points with bridges