Articulation Points in Graph in DSA C#

Mental Model

An articulation point is a node in a graph that, if removed, breaks the graph into more pieces. It shows where the graph is fragile.

Analogy: Imagine a city connected by roads. Some intersections are so important that if they close, parts of the city become unreachable. Those intersections are articulation points.

Graph:
  1
 / \
2 - 3 - 4
     |
     5

Articulation points: 3 (removing 3 splits the graph)

Dry Run Walkthrough

Input: Graph with edges: 1-2, 1-3, 2-3, 3-4, 3-5; find articulation points

Goal: Identify nodes that, if removed, increase the number of disconnected parts

Step 1: Start DFS from node 1, set discovery time and low value

Visited: 1 (disc=1, low=1)

Why: We begin exploring the graph to assign discovery times

Step 2: Visit node 2 from 1, set disc=2, low=2

Visited: 1 (disc=1, low=1), 2 (disc=2, low=2)

Why: We explore neighbors to find back edges and articulation points

Step 3: Visit node 3 from 2, set disc=3, low=3; back edge to 1 (visited, not parent), low[3]=min(3,1)=1

Visited: 1(1,1), 2(2,2), 3(3,1)

Why: Back edge to ancestor 1 updates low[3] to 1

Step 4: From 3, visit 4, set disc=4, low=4; no further neighbors, backtrack

Visited: 1(1,1),2(2,2),3(3,1),4(4,4)

Why: Leaf node 4; update low[3]=min(1,4)=1; low[4]>=disc[3] (4>=3) => 3 is AP

Step 5: From 3, visit 5, set disc=5, low=5; no further, backtrack

Visited all; low[3]=min(1,5)=1; low[5]>=3 => 3 is AP

Why: Another leaf from 3 confirms AP status

Step 6: Backtrack to 2, low[2]=min(2, low[3]=1)=1

low[2]=1; check low[3]=1 >= disc[2]=2? No => 2 not AP

Why: Low value from subtree reaches ancestor of 2 via back edge

Step 7: Backtrack to 1, low[1]=min(1, low[2]=1)=1; next neighbor 3 visited, back edge low[1]=min(1,3)=1

low[1]=1; root children=1 (only 2) => 1 not AP

Why: Root has only one DFS child; back edge to 3 doesn't add child

Result:

Articulation points: 3

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

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

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

    private void APUtil(int u, bool[] visited, int[] disc, int[] low, int[] parent, bool[] ap, ref int time) {
        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, ref time);

                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 FindArticulationPoints() {
        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;
        }

        int time = 0;

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

        Console.Write("Articulation points: ");
        bool first = true;
        for (int i = 0; i < V; i++) {
            if (ap[i]) {
                if (!first) Console.Write(", ");
                Console.Write(i + 1);
                first = false;
            }
        }
        Console.WriteLine();
    }
}

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

        g.FindArticulationPoints();
    }
}

disc[u] = low[u] = ++time;

Assign discovery time and low value when visiting node u

parent[v] = u; APUtil(v, visited, disc, low, parent, ap, ref time);

Explore child v of u recursively

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

Update low[u] based on child's low value

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

Root node with multiple children is articulation point

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

Non-root node u is articulation point if child's low >= u's discovery

} else if (v != parent[u]) { low[u] = Math.Min(low[u], disc[v]);

Update low[u] for back edges to ancestors

Output

Articulation points: 3

Complexity Analysis

Time: O(V + E) because we visit each vertex and edge once during DFS

Space: O(V) for arrays storing discovery, low, parent, visited, and articulation flags

vs Alternative: Naive approach would remove each node and check connectivity repeatedly, costing O(V*(V+E))

Edge Cases

Graph with no edges

No articulation points because no connections to break

DSA C#

if (!visited[i]) { APUtil(i, visited, disc, low, parent, ap, ref time); }

Graph with single node

No articulation points because removing the only node leaves empty graph

DSA C#

Root has 0 children

Graph with multiple disconnected components

Algorithm runs DFS on each component separately to find articulation points

DSA C#

for (int i = 0; i < V; i++) { if (!visited[i]) { APUtil(...); } }

When to Use This Pattern

When a problem asks for nodes whose removal disconnects the graph, use articulation points detection with DFS low-link values.

Common Mistakes

Mistake: Forgetting to update low[u] for back edges
Fix: Use 'else if (v != parent[u]) low[u] = Math.Min(low[u], disc[v]);'

Mistake: Marking root as AP without checking children > 1
Fix: Count children only for root and mark only if >1

Mistake: Not handling multiple components
Fix: Loop over all nodes and call APUtil if unvisited

Summary

Find nodes that disconnect the graph if removed.

Use when you want to find fragile points in networks or graphs.

Track discovery and low times during DFS to identify articulation points.

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