Articulation Points in Graph in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the discovery time array with -1 for all vertices.

DSA Typescript

const disc: number[] = new Array(V).fill([1]);

Drag options to blanks, or click blank then click option'

Anull

B0

C-1

DInfinity

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of -1 causes confusion with valid discovery times.

Using null or Infinity is not standard for discovery times.

We initialize discovery times with -1 to indicate unvisited vertices.

2fill in blank

medium

Complete the code to update the low time of u after visiting v.

DSA Typescript

low[u] = Math.min(low[u], [1]);

Drag options to blanks, or click blank then click option'

Alow[v]

Bdisc[u]

Cdisc[v]

Dlow[u]

Attempts:

3 left

💡 Hint

Common Mistakes

Using disc[v] instead of low[v] misses back edges.

Using disc[u] or low[u] does not update correctly.

We update low[u] with the minimum low[v] to track earliest reachable ancestor.

3fill in blank

hard

Fix the error in the condition to check if u is an articulation point when u is root.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

Avisited[u]

Blow[u]

Cdisc[u]

Dchildren

Attempts:

3 left

💡 Hint

Common Mistakes

Using low[u] or disc[u] instead of children count.

Checking visited[u] is irrelevant here.

Root u is articulation point if it has more than one child in DFS tree.

4fill in blank

hard

Fill both blanks to check if u is an articulation point when u is not root.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

Alow[v]

Bdisc[u]

Clow[u]

Ddisc[v]

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping low[v] and disc[u] in condition.

Using low[u] or disc[v] incorrectly.

If low[v] >= disc[u], u is an articulation point for non-root nodes.

5fill in blank

hard

Fill all three blanks to complete the DFS function signature and initial call.

DSA Typescript

function dfs([1], [2], [3]) {
  // DFS logic here
}
dfs(0, -1, time);

Drag options to blanks, or click blank then click option'

Au

Bparent

Ctime

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Using visited instead of parent or time in parameters.

Incorrect order of parameters.

DFS function takes current node u, its parent, and current time.