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 with -1.

DSA C

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

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

A0

B-1

C1

DINT_MAX

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing discovery time to 0 causes confusion with actual discovery time.

Using INT_MAX is unnecessary and can cause overflow.

Initializing discovery times to -1 indicates that the vertex has not been visited yet.

2fill in blank

medium

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

DSA C

low[u] = [1](low[u], low[v]);

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

Amin

Babs

Cmax

Dpow

Attempts:

3 left

💡 Hint

Common Mistakes

Using max instead of min leads to incorrect articulation point detection.

Using abs or pow is irrelevant here.

We update low[u] to the minimum of its current low[u] and low[v] to track the earliest visited vertex reachable.

3fill in blank

hard

Complete the code to update the low time of u when v is already visited.

DSA C

if (v != parent[u])
    low[u] = [1](low[u], disc[v]);

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

Amin

Bpow

Cabs

Dmax

Attempts:

3 left

💡 Hint

Common Mistakes

Using max causes wrong articulation point detection.

Using abs or pow is incorrect.

We update low[u] to the minimum of low[u] and disc[v] to consider back edges.

4fill in blank

hard

Fill both blanks to check if u is an articulation point for root and non-root cases.

DSA C

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

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

Achildren

Bdisc[u]

Clow[u]

Dtime

Attempts:

3 left

💡 Hint

Common Mistakes

Using low[u] instead of disc[u] in second condition.

Checking children count incorrectly for root.

Root u is articulation point if it has more than one child. For non-root, if low[v] >= disc[u], u is articulation point.

5fill in blank

hard

Fill all three blanks to correctly implement the DFS function for articulation points.

DSA C

void APUtil(int u, bool visited[], int disc[], int low[], int parent[], bool ap[]) {
    static int [1] = 0;
    int [2] = 0;
    visited[u] = true;
    disc[u] = low[u] = ++[1];

    for (int v : adj[u]) {
        if (!visited[v]) {
            parent[v] = u;
            [2]++;
            APUtil(v, visited, disc, low, parent, ap);
            low[u] = min(low[u], low[v]);

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

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

Atime

Bchildren

Ccount

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Using non-static variable for time causes incorrect discovery times.

Using wrong variable names for children count.

Static variable 'time' tracks discovery order. 'children' counts children of u. 'time' is incremented for discovery time.

Practice

1. What is an articulation point in a graph?

easy

A. A vertex that has no edges connected to it

B. A vertex with the highest degree in the graph

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

D. A vertex connected to all other vertices

Solution

1. Step 1: Understand articulation point definition

   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 C

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

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

easy

A. int graph[100][100];

B. vector<int> graph[100];

C. int* graph = malloc(sizeof(int) * 100);

D. int graph[100];

Solution

1. Step 1: Understand adjacency list representation

   An adjacency list stores neighbors for each vertex, best done with an array of vectors in C++ or array of lists in C.

2. Step 2: Analyze options

   vector<int> graph[100];: vector<int> graph[100]; is correct for adjacency list in C++ (common in DSA). int graph[100][100]; is 2D array (adjacency matrix). int* graph = malloc(sizeof(int) * 100); is incorrect memory allocation. int graph[100]; is single array, insufficient for lists.

3. Final Answer:

   vector<int> graph[100]; -> Option B

4. Quick Check:

   Adjacency list = array of vectors [OK]

Hint: Use array of vectors for adjacency list in C++ [OK]

Common Mistakes:

• Using 2D arrays for adjacency list instead of adjacency matrix
• Incorrect memory allocation for adjacency list
• Confusing adjacency list with adjacency matrix

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

void dfs(int u, int parent) {
  visited[u] = true;
  disc[u] = low[u] = ++time;
  int children = 0;
  for (int v : graph[u]) {
    if (!visited[v]) {
      children++;
      dfs(v, u);
      low[u] = min(low[u], low[v]);
      if (parent == -1 && children > 1)
        articulation[u] = true;
      if (parent != -1 && low[v] >= disc[u])
        articulation[u] = true;
    } else if (v != parent) {
      low[u] = min(low[u], disc[v]);
    }
  }
}

What will be the value of articulation[1] after running dfs(0, -1) on the graph edges: 0-1, 1-2, 1-3?

medium

A. true

B. false

C. undefined

D. depends on order

Solution

1. Step 1: Analyze graph structure and DFS

   Graph edges: 0-1, 1-2, 1-3. Vertex 1 connects 0 to 2 and 3. Removing 1 disconnects graph.

2. Step 2: Apply articulation point logic

   Since 1 is not root (parent != -1) and low[v] >= disc[u] condition holds for children 2 and 3, articulation[1] is set true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Vertex 1 disconnects graph = articulation true [OK]

Hint: Check if removing vertex splits graph [OK]

Common Mistakes:

• Assuming root node logic applies to vertex 1
• Ignoring low and disc comparison
• Confusing parent and child roles in DFS

4. The following code snippet is intended to find articulation points but has a bug. What is the bug?

void dfs(int u, int parent) {
  visited[u] = true;
  disc[u] = low[u] = ++time;
  int children = 0;
  for (int v : graph[u]) {
    if (!visited[v]) {
      children++;
      dfs(v, u);
      low[u] = min(low[u], low[v]);
      if (parent == -1 && children > 1)
        articulation[u] = true;
      if (parent != -1 && low[v] > disc[u])
        articulation[u] = true;
    } else if (v != parent) {
      low[u] = min(low[u], disc[v]);
    }
  }
}

medium

A. The visited array is not updated

B. The variable children is not incremented

C. The parent parameter is not passed correctly

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

Solution

1. Step 1: Review articulation point condition

   The condition for articulation point when parent != -1 is low[v] >= disc[u], not strictly greater.

2. Step 2: Identify impact of wrong condition

   Using low[v] > disc[u] misses cases where low[v] == disc[u], causing missed articulation points.

3. Final Answer:

   The condition low[v] > disc[u] should be low[v] >= disc[u] -> Option D

4. Quick Check:

   Use >= to detect articulation points correctly [OK]

Hint: Use >= not > for articulation condition [OK]

Common Mistakes:

• Using > instead of >= in low and disc comparison
• Forgetting to increment children count
• Not marking visited vertices

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

hard

A. [1,3]

B. [1,4]

C. [0,2,4]

D. [3,5]

Solution

1. Step 1: Analyze graph structure

   Triangles: 0-1-2 and 3-4-5. Vertex 1 connects 0-1-2 triangle to 3-4-5 cluster via 1-3. Vertex 3 connects 1 to the 3-4-5 triangle.

2. Step 2: Identify articulation points

   Removing 1 disconnects {0,2} from {3,4,5}. Removing 3 disconnects {0,1,2} from {4,5} (4-5 still connected). So articulation points are 1 and 3.

3. Final Answer:

   [1,3] -> Option A

4. Quick Check:

   Vertices splitting graph = 1 and 3 [OK]

Hint: Check vertices connecting separate cycles [OK]

Common Mistakes:

• Including vertices inside cycles as articulation points
• Missing articulation points connecting clusters
• Confusing articulation points with bridges