Articulation Points in Graph in DSA C# - Build from Scratch

Articulation Points in Graph

📖 Scenario: Imagine a city's road network represented as a graph. Each intersection is a node, and roads are edges connecting them. Some intersections are critical: if they close, parts of the city become unreachable. These are called articulation points.

🎯 Goal: You will build a program to find all articulation points in a given undirected graph using Depth First Search (DFS). This helps identify critical intersections in the city.

📋 What You'll Learn

Create an adjacency list to represent the graph

Use arrays to track discovery times and low values of nodes

Implement DFS to find articulation points

Print all articulation points found in the graph

💡 Why This Matters

🌍 Real World

Finding articulation points helps city planners identify critical intersections that, if blocked, can disrupt traffic flow.

💼 Career

Understanding articulation points is important for network reliability analysis, infrastructure planning, and cybersecurity.

1

Create the graph adjacency list

Create a dictionary called graph to represent the undirected graph with these exact edges: 0-1, 1-2, 2-0, 1-3, 3-4. Use Dictionary> and add neighbors for each node.

DSA C#

# Your code here to create the graph adjacency list

Hint

Use a dictionary where keys are node numbers and values are lists of connected nodes.

2

Set up helper arrays and variables

Add integer arrays called disc and low of size 5 initialized with -1. Create a boolean array called visited of size 5 initialized with false. Also create a boolean array called articulationPoints of size 5 initialized with false. Create an integer variable time and set it to 0.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>();
        graph[0] = new List { 1, 2 };
        graph[1] = new List { 0, 2, 3 };
        graph[2] = new List { 0, 1 };
        graph[3] = new List { 1, 4 };
        graph[4] = new List { 3 };

        // Initialize arrays and variables
        // Your code here
    }
}

Hint

Initialize arrays with size 5 and set default values using a for loop.

3

Implement DFS to find articulation points

Add a static method DFS with parameters int u, int parent, Dictionary<int, List<int>> graph, int[] disc, int[] low, bool[] visited, bool[] articulationPoints, and ref int time. Inside Main, call DFS(0, -1, graph, disc, low, visited, articulationPoints, ref time);. Implement DFS to update disc, low, and mark articulation points correctly using the standard algorithm for articulation points in undirected graphs.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>();
        graph[0] = new List { 1, 2 };
        graph[1] = new List { 0, 2, 3 };
        graph[2] = new List { 0, 1 };
        graph[3] = new List { 1, 4 };
        graph[4] = new List { 3 };

        int[] disc = new int[5];
        int[] low = new int[5];
        bool[] visited = new bool[5];
        bool[] articulationPoints = new bool[5];
        int time = 0;

        for (int i = 0; i > graph, int[] disc, int[] low, bool[] visited, bool[] articulationPoints, ref int time)
    {
        // Your code here
    }
}

Hint

Use DFS with discovery and low times. Track children count for root. Update articulation points when conditions meet.

4

Print all articulation points

Add a for loop from 0 to 4. Inside the loop, if articulationPoints[i] is true, print "Articulation Point: " + i.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>();
        graph[0] = new List { 1, 2 };
        graph[1] = new List { 0, 2, 3 };
        graph[2] = new List { 0, 1 };
        graph[3] = new List { 1, 4 };
        graph[4] = new List { 3 };

        int[] disc = new int[5];
        int[] low = new int[5];
        bool[] visited = new bool[5];
        bool[] articulationPoints = new bool[5];
        int time = 0;

        for (int i = 0; i > graph, int[] disc, int[] low, bool[] visited, bool[] articulationPoints, ref int time)
    {
        visited[u] = true;
        disc[u] = time;
        low[u] = time;
        time++;
        int children = 0;

        foreach (int v in graph[u])
        {
            if (!visited[v])
            {
                children++;
                DFS(v, u, graph, disc, low, visited, articulationPoints, ref time);
                low[u] = Math.Min(low[u], low[v]);

                if (parent != -1 && low[v] >= disc[u])
                {
                    articulationPoints[u] = true;
                }
            }
            else if (v != parent)
            {
                low[u] = Math.Min(low[u], disc[v]);
            }
        }

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

Hint

Loop through the articulationPoints array and print the node number if true.

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