Articulation point

Moderate

0/80

13 upvotes

Asked in companies

Problem statement

You are given an undirected unweighted graph and you are supposed to find all articulation in the graph.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input will contain T(number of test cases), each test case follows as.
Line1: contain two space-separated integers denoting the number of vertex and number of edges in the graph respectively.
Next M lines contain two space-separated integers u and v denoting the edge between u and v

Output Format:

For each test case print the list of articulation points in sorted order in a new line.

Constraints:

1 <= T <= 100
1 <= N, M <= 10^4
1 <= u, v <= N

Sample Input:

Sample Output:

Approaches (1)

Approach 1

Articulation point

Time Complexity

Time complexity: O(N*log(N) + M)

Space Complexity

(100% EXP penalty)

Articulation point

Console