Articulation Points in Graph in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an articulation point in a graph?

An articulation point (or cut vertex) is a vertex in a graph that, if removed along with its edges, increases the number of connected components in the graph.

intermediate

Which algorithm is commonly used to find articulation points in a graph?

Tarjan's algorithm uses Depth First Search (DFS) along with discovery and low times to find articulation points efficiently.

intermediate

In Tarjan's algorithm, what does the 'low' value represent for a vertex?

The 'low' value of a vertex is the earliest discovery time reachable from that vertex or its descendants by following DFS tree edges and back edges.

intermediate

Why is the root of the DFS tree a special case when finding articulation points?

The root is an articulation point only if it has two or more children in the DFS tree because removing it would disconnect those children.

intermediate

What is the time complexity of finding articulation points using Tarjan's algorithm?

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, because it uses a single DFS traversal.

What happens if you remove an articulation point from a connected graph?

A The graph becomes disconnected

B The graph remains connected

C The graph becomes a tree

D The graph loses all edges

Removing an articulation point increases the number of connected components, making the graph disconnected.

In Tarjan's algorithm, what does a back edge indicate?

A An edge to a sibling in DFS tree

B An edge to a descendant in DFS tree

C An edge to an ancestor in DFS tree

D An edge to a disconnected vertex

A back edge connects a vertex to one of its ancestors in the DFS tree, helping update low values.

Which condition identifies a non-root vertex as an articulation point in Tarjan's algorithm?

A If it has no children

B If it is the last vertex visited

C If it has a child with low[child] < discovery[vertex]

D If it has a child with low[child] >= discovery[vertex]

If a child cannot reach an ancestor of the vertex, removing the vertex disconnects the child subtree.

What data structure is primarily used in Tarjan's algorithm to find articulation points?

A Depth First Search recursion

B Queue

C Stack

D Priority Queue

Tarjan's algorithm uses DFS recursion to explore vertices and compute discovery and low times.

How many times is each vertex visited in Tarjan's algorithm?

A Never

B Once

C Multiple times depending on edges

D Twice

Each vertex is visited once during the DFS traversal, making the algorithm efficient.

Explain how Tarjan's algorithm finds articulation points in a graph.

Think about how DFS explores and tracks earliest reachable vertices.

Describe why removing an articulation point increases the number of connected components in a graph.

Consider the graph as a network of roads and articulation points as bridges.

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