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.