Articulation Points in Graph in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

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

DSA C#

int[] disc = new int[n];
for (int i = 0; i < n; i++) {
    disc[i] = [1];
}

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

Aint.MaxValue

B0

C-1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing discovery time to 0 causes confusion with valid discovery times.

Using int.MaxValue is unnecessary and less clear.

Discovery times are initialized to -1 to indicate unvisited vertices.

2fill in blank

medium

Complete the code to update the low time of the current vertex after visiting a child.

DSA C#

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

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

Alow[v]

Bdisc[v]

Cdisc[u]

Dtime

Attempts:

3 left

💡 Hint

Common Mistakes

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

Using disc[u] or time is incorrect for this update.

Low time of u is updated with the low time of its child v.

3fill in blank

hard

Fix the error in the condition to check if the current vertex is an articulation point (not root).

DSA C#

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

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

Adisc[v]

Btime

Clow[u]

Ddisc[u]

Attempts:

3 left

💡 Hint

Common Mistakes

Using low[u] instead of disc[u] breaks the articulation point logic.

Comparing with disc[v] or time is incorrect.

We compare low[v] with disc[u] to check if v or its descendants can reach an ancestor of u.

4fill in blank

hard

Fill both blanks to complete the DFS call and update the child count for root articulation point check.

DSA C#

for (int v = 0; v < graph[u].Count; v++) {
    int w = graph[u][v];
    if (disc[w] == -1) {
        parent[w] = u;
        [1]++;
        DFS(w, [2]);
    }
}

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

Achildren

Btime

Cu

Ddisc

Attempts:

3 left

💡 Hint

Common Mistakes

Passing time instead of u as parent in DFS call.

Incrementing wrong variable instead of children.

We increment children count and call DFS on child vertex w with current vertex u.

5fill in blank

hard

Fill all three blanks to complete the root articulation point condition and mark it.

DSA C#

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

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

Achildren

B1

Cap

Dtime

Attempts:

3 left

💡 Hint

Common Mistakes

Using time instead of 1 in comparison.

Marking wrong array or variable.

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

Practice

1. What is an articulation point in a graph?

easy

A. A vertex that forms a cycle with other vertices

B. A vertex with the highest degree in the graph

C. A vertex that has no edges connected to it

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

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 D

4. Quick Check:

   Articulation point = vertex increasing components when removed [OK]

Hint: Articulation point splits graph if removed [OK]

Common Mistakes:

• Confusing articulation point with highest degree vertex
• Thinking articulation point is a vertex with no edges
• Mixing articulation point with cycle formation

2. Which of the following is the correct C# method signature to find articulation points in a graph represented as adjacency list?

easy

A. public void FindArticulationPoints(List<int>[] graph, int vertices)

B. public int FindArticulationPoints(int[][] graph)

C. public bool FindArticulationPoints(Dictionary graph)

D. public void FindArticulationPoints(int[] graph, int vertices)

Solution

1. Step 1: Identify common graph representation in C#

   Adjacency list is often represented as List<int>[] for vertices count known.

2. Step 2: Check method signature compatibility

   public void FindArticulationPoints(List<int>[] graph, int vertices) uses List<int>[] and vertices count, suitable for articulation point algorithm.

3. Final Answer:

   public void FindArticulationPoints(List<int>[] graph, int vertices) -> Option A

4. Quick Check:

   Adjacency list with vertex count = correct signature [OK]

Hint: Use List<int>[] and vertex count for adjacency list [OK]

Common Mistakes:

• Using 2D array instead of adjacency list
• Returning int or bool instead of void
• Using Dictionary without vertex count parameter

3. Given the following graph edges:
0 - 1, 1 - 2, 2 - 0, 1 - 3
Which vertex is an articulation point?

medium

A. Vertex 0

B. Vertex 3

C. Vertex 1

D. Vertex 2

Solution

1. Step 1: Visualize the graph connections

   Vertices 0,1,2 form a triangle (cycle). Vertex 3 connects only to 1.

2. Step 2: Identify articulation points

   Removing vertex 1 disconnects vertex 3 from the rest, increasing components. Others do not disconnect graph.

3. Final Answer:

   Vertex 1 -> Option C

4. Quick Check:

   Removing vertex 1 splits graph = articulation point [OK]

Hint: Check if removing vertex disconnects graph [OK]

Common Mistakes:

• Assuming all vertices in cycle are articulation points
• Ignoring leaf vertex connections
• Confusing vertex numbers

4. Consider this C# code snippet to find articulation points:

void DFS(int u, int parent) {
  visited[u] = true;
  disc[u] = low[u] = time++;
  int children = 0;
  foreach(var v in graph[u]) {
    if (!visited[v]) {
      children++;
      DFS(v, u);
      low[u] = Math.Min(low[u], low[v]);
      if (parent != -1 && low[v] >= disc[u])
        articulation[u] = true;
    } else if (v != parent) {
      low[u] = Math.Min(low[u], disc[v]);
    }
  }
  if (parent == -1 && children > 1)
    articulation[u] = true;
}

What is the bug in this code?

medium

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

B. The variable 'time' is not initialized or incremented properly

C. The check 'v != parent' is incorrect and should be removed

D. The articulation array should be reset inside DFS

Solution

1. Step 1: Analyze usage of 'time' variable

   'time' is used to assign discovery times but code snippet does not show initialization or global declaration.

2. Step 2: Check other conditions

   Conditions and logic for articulation points are correct; 'time' must be properly initialized and incremented outside DFS.

3. Final Answer:

   The variable 'time' is not initialized or incremented properly -> Option B

4. Quick Check:

   Uninitialized 'time' breaks discovery time tracking [OK]

Hint: Initialize and increment 'time' outside DFS [OK]

Common Mistakes:

• Changing correct condition to strict inequality
• Removing parent check causing wrong low updates
• Resetting articulation inside DFS causing wrong results

5. You have a connected graph with 5 vertices and edges:
0-1, 1-2, 2-0, 1-3, 3-4
Which vertices are articulation points?

hard

A. [1, 3]

B. [0, 2]

C. [3, 4]

D. [1, 4]

Solution

1. Step 1: Visualize the graph structure

   Vertices 0,1,2 form a triangle. Vertex 3 connects to 1 and 4. Vertex 4 is leaf.

2. Step 2: Identify articulation points

   Removing 1 disconnects 3 and 4. Removing 3 disconnects 4. Vertices 0,2 are in cycle, not articulation points. Vertex 4 is leaf, not articulation.

3. Final Answer:

   [1, 3] -> Option A

4. Quick Check:

   Vertices disconnecting graph when removed = [1, 3] [OK]

Hint: Check vertices whose removal disconnects others [OK]

Common Mistakes:

• Including leaf vertex as articulation point
• Confusing cycle vertices as articulation points
• Missing vertex 3 as articulation point