Articulation Points in Graph in DSA C# - 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 C# code that finds articulation points in a graph?

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    int V;
    List<int>[] adj;

    int time = 0;

    public Graph(int v) {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; i++)
            adj[i] = new List<int>();
    }

    public void AddEdge(int u, int v) {
        adj[u].Add(v);
        adj[v].Add(u);
    }

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

        foreach (int v in adj[u]) {
            if (!visited[v]) {
                children++;
                parent[v] = u;
                APUtil(v, visited, disc, low, parent, ap);

                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]);
            }
        }
    }

    public void AP() {
        bool[] visited = new bool[V];
        int[] disc = new int[V];
        int[] low = new int[V];
        int[] parent = new int[V];
        bool[] ap = new bool[V];

        for (int i = 0; i < V; i++) {
            parent[i] = -1;
            visited[i] = false;
            ap[i] = false;
        }

        for (int i = 0; i < V; i++) {
            if (!visited[i])
                APUtil(i, visited, disc, low, parent, ap);
        }

        for (int i = 0; i < V; i++) {
            if (ap[i])
                Console.Write(i + " ");
        }
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(5);
        g.AddEdge(1, 0);
        g.AddEdge(0, 2);
        g.AddEdge(2, 1);
        g.AddEdge(0, 3);
        g.AddEdge(3, 4);

        g.AP();
    }
}

A 0 1 3

B 1 3

C 0 3

D 3 4

💡 Hint

Think about which nodes, if removed, increase the number of connected components.

The articulation points are nodes 0 and 3 because removing either disconnects the graph.

🧠 Conceptual

intermediate

Understanding articulation points in a graph

Which of the following best describes an articulation point in a 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.

D A vertex that has no edges connected to it.

💡 Hint

Think about the effect of removing a vertex on the graph's connectivity.

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

🔧 Debug

advanced

Identify the error in articulation points code snippet

What error will the following code produce when run?

DSA C#

int[] parent = new int[V];
for (int i = 0; i < V; i++) {
    parent[i] = 0;
}
// Later in DFS
if (parent[u] == -1 && children > 1)
    ap[u] = true;

A Logical error: root node check fails because parent array is initialized with 0 instead of -1.

B No error; code runs correctly.

C Runtime error: IndexOutOfRangeException.

D Syntax error: missing semicolon.

💡 Hint

Check how the root node is identified in the articulation point algorithm.

The root node is identified by parent[u] == -1, but initializing parent array with 0 causes incorrect root detection.

❓ Predict Output

advanced

Output of articulation points in a disconnected graph

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

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    int V;
    List<int>[] adj;
    int time = 0;

    public Graph(int v) {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; i++)
            adj[i] = new List<int>();
    }

    public void AddEdge(int u, int v) {
        adj[u].Add(v);
        adj[v].Add(u);
    }

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

        foreach (int v in adj[u]) {
            if (!visited[v]) {
                children++;
                parent[v] = u;
                APUtil(v, visited, disc, low, parent, ap);

                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]);
            }
        }
    }

    public void AP() {
        bool[] visited = new bool[V];
        int[] disc = new int[V];
        int[] low = new int[V];
        int[] parent = new int[V];
        bool[] ap = new bool[V];

        for (int i = 0; i < V; i++) {
            parent[i] = -1;
            visited[i] = false;
            ap[i] = false;
        }

        for (int i = 0; i < V; i++) {
            if (!visited[i])
                APUtil(i, visited, disc, low, parent, ap);
        }

        for (int i = 0; i < V; i++) {
            if (ap[i])
                Console.Write(i + " ");
        }
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(7);
        g.AddEdge(0, 1);
        g.AddEdge(1, 2);
        g.AddEdge(2, 0);
        g.AddEdge(1, 3);
        g.AddEdge(3, 4);
        g.AddEdge(4, 5);
        g.AddEdge(5, 3);
        g.AddEdge(5, 6);

        g.AP();
    }
}

A 3 5

B 1 3 5

C 1 3 4 5

D 0 1 3 5

💡 Hint

Check articulation points in each connected component separately.

Nodes 1, 3, and 5 are articulation points because their removal increases connected components.

🧠 Conceptual

expert

Articulation points and bridges relationship

Which statement correctly describes the relationship between articulation points and bridges in a graph?

A Every articulation point is connected to at least one bridge, but not every bridge connects to an articulation point.

B Every bridge connects two articulation points, and every articulation point connects at least two bridges.

C Articulation points and bridges are the same; both refer to edges that disconnect the graph.

D Every bridge is an edge whose removal increases connected components; articulation points are vertices whose removal increases connected components; they are related but distinct concepts.

💡 Hint

Think about the difference between vertices and edges in graph connectivity.

Bridges are edges that increase connected components when removed; articulation points are vertices with similar property. They are related but not the same.

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