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

DSA Java

import java.util.*;

public class Graph {
    private int V;
    private LinkedList<Integer>[] adj;
    private int time = 0;

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

    void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

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

        for (int v : 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]);
            }
        }
    }

    void findAP() {
        boolean[] visited = new boolean[V];
        int[] disc = new int[V];
        int[] low = new int[V];
        int[] parent = new int[V];
        boolean[] ap = new boolean[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])
                System.out.print(i + " ");
        }
    }

    public static void main(String[] args) {
        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.findAP();
    }
}

A 0 1 3

B 1 3

C 0 3

D 3 4

💡 Hint

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

Vertices 0 and 3 are articulation points because removing them disconnects parts of the graph. Vertex 0 connects the triangle (0,1,2) with vertex 3 and 4. Vertex 3 connects vertex 4 to the rest.

🧠 Conceptual

intermediate

Understanding articulation points in a graph

Which of the following statements about articulation points in an undirected graph is TRUE?

A An articulation point is a vertex that, when removed, increases the number of connected components.

B An articulation point is a vertex that has no edges connected to it.

C An articulation point is a vertex with the highest degree in the graph.

D An articulation point is a vertex that lies on every cycle in the graph.

💡 Hint

Think about what happens to connectivity when a vertex is removed.

An articulation point is defined as a vertex whose removal increases the number of connected components in the graph.

🔧 Debug

advanced

Identify the error in articulation points code snippet

What error will the following Java code produce when run?

DSA Java

int[] parent = new int[V];
boolean[] visited = new boolean[V];
int[] disc = new int[V];
int[] low = new int[V];
boolean[] ap = new boolean[V];

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

APUtil(0, visited, disc, low, parent, ap);

A Logical error: parent initialization should be -1, not 0

B No error, code runs correctly

C NullPointerException at APUtil call

D ArrayIndexOutOfBoundsException during APUtil execution

💡 Hint

Check the initialization of parent array and its effect on root detection.

Parent array should be initialized to -1 to indicate no parent. Initializing to 0 causes incorrect root detection and may lead to wrong articulation point results.

🚀 Application

advanced

Number of articulation points in a complex graph

Given a graph with 7 vertices and edges: (0-1), (1-2), (2-0), (1-3), (1-4), (1-6), (3-5), (4-5), how many articulation points does it have?

A 4

B 2

C 3

D 1

💡 Hint

Identify vertices whose removal disconnects the graph.

Vertices 1 and 3 are articulation points. Removing 1 disconnects vertices 3,4,5,6; removing 3 disconnects vertex 5.

❓ Predict Output

expert

Output of articulation points detection on a disconnected graph

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

DSA Java

import java.util.*;

public class Graph {
    private int V;
    private LinkedList<Integer>[] adj;
    private int time = 0;

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

    void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

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

        for (int v : 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]);
            }
        }
    }

    void findAP() {
        boolean[] visited = new boolean[V];
        int[] disc = new int[V];
        int[] low = new int[V];
        int[] parent = new int[V];
        boolean[] ap = new boolean[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])
                System.out.print(i + " ");
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph(7);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(1, 3);
        g.addEdge(1, 4);
        g.addEdge(1, 6);
        g.addEdge(3, 5);
        g.addEdge(4, 5);

        g.findAP();
    }
}

A 0 1 3

B 3 5

C 1 4

D 1 3

💡 Hint

Consider articulation points in each connected component separately.

Vertices 1 and 3 are articulation points. Vertex 1 connects multiple parts, and vertex 3 connects vertex 5.

Practice

1. What is an articulation point in a graph?

easy

A. A vertex that forms a cycle in the graph

B. A vertex with the highest degree in the graph

C. A vertex connected to all other vertices

D. A vertex which, 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 which, when removed, increases the number of connected components matches this definition exactly.

3. Final Answer:

   A vertex which, when removed, increases the number of connected components -> Option D

4. Quick Check:

   Articulation point = vertex breaking connectivity [OK]

Hint: Articulation point breaks graph connectivity when removed [OK]

Common Mistakes:

• Confusing articulation point with highest degree vertex
• Thinking articulation point forms cycles
• Assuming articulation point connects to all vertices

2. Which of the following is the correct way to declare a graph adjacency list in Java for articulation point detection?

easy

A. int graph[][] = new int[];

B. HashMap graph = new HashMap<>();

C. ArrayList graph = new ArrayList<>();

D. List<Integer> graph = new List<>();

Solution

1. Step 1: Understand adjacency list structure

   An adjacency list for a graph is usually a list of lists, where each inner list holds neighbors of a vertex.

2. Step 2: Check Java syntax for adjacency list

   ArrayList graph = new ArrayList<>(); correctly declares an ArrayList of ArrayLists of Integers, suitable for adjacency list.

3. Final Answer:

   ArrayList graph = new ArrayList<>(); -> Option C

4. Quick Check:

   Adjacency list = list of lists [OK]

Hint: Adjacency list uses list of lists in Java [OK]

Common Mistakes:

• Using 2D array without size initialization
• Using HashMap with wrong value type
• Trying to instantiate interface List directly

3. Consider the following Java code snippet for articulation point detection. What will be the output when the graph has edges: 0-1, 1-2, 1-3?

int V = 4;
ArrayList graph = new ArrayList<>();
for (int i = 0; i < V; i++) graph.add(new ArrayList<>());
graph.get(0).add(1);
graph.get(1).add(0);
graph.get(1).add(2);
graph.get(2).add(1);
graph.get(1).add(3);
graph.get(3).add(1);
// Articulation points found: 1

medium

A. []

B. [1]

C. [2, 3]

D. [0, 1]

Solution

1. Step 1: Analyze the graph structure

   The graph has vertices 0,1,2,3 with edges 0-1, 1-2, 1-3. Vertex 1 connects to all others.

2. Step 2: Identify articulation points

   Removing vertex 1 disconnects the graph into three parts, so 1 is an articulation point. Others are not.

3. Final Answer:

   [1] -> Option B

4. Quick Check:

   Only vertex 1 breaks connectivity [OK]

Hint: Check which vertex removal splits graph [OK]

Common Mistakes:

• Assuming leaf nodes are articulation points
• Including vertices with degree 1 as articulation points
• Ignoring connectivity after removal

4. The following Java code snippet is intended to find articulation points but has a bug. What is the error?

void dfs(int u, int parent) {
  visited[u] = true;
  disc[u] = low[u] = time++;
  int children = 0;
  for (int v : graph.get(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;
}

medium

A. The time variable is not initialized before DFS

B. The condition for root articulation point is incorrect

C. The low array is not updated correctly for back edges

D. The visited array is not marked true for vertex u

Solution

1. Step 1: Check initialization of time variable

   The variable 'time' is used to assign discovery times but must be initialized before DFS starts.

2. Step 2: Verify other parts of DFS

   Conditions for root and back edges are correct; visited[u] is marked true properly.

3. Final Answer:

   The time variable is not initialized before DFS -> Option A

4. Quick Check:

   Uninitialized time causes wrong discovery times [OK]

Hint: Initialize time counter before DFS call [OK]

Common Mistakes:

• Forgetting to initialize time before DFS
• Misusing parent check for root node
• Not updating low values for back edges

5. Given a connected undirected 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]

D. [1]

Solution

1. Step 1: Analyze the graph structure

   Vertices 0,1,2 form a triangle (cycle). Edges 1-3 and 3-4 form a chain attached to vertex 1.

2. Step 2: Identify articulation points

   Removing vertex 1 disconnects 3 and 4 from the cycle, so 1 is an articulation point. Removing 3 disconnects 4, so 3 is also an articulation point. Vertices 0 and 2 are in a cycle, so not articulation points.

3. Final Answer:

   [1, 3] -> Option A

4. Quick Check:

   Vertices breaking connectivity: 1 and 3 [OK]

Hint: Check vertices whose removal splits graph into parts [OK]

Common Mistakes:

• Assuming cycle vertices are articulation points
• Missing vertex 3 as articulation point
• Only considering vertex 1 as articulation point