Last Updated: 29 Nov, 2021

Beautiful Vertices

Hard

Asked in companies

Solve now

Problem statement

You are given an undirected graph containing ‘N’ vertices that are connected by ‘M’ edges. Your task is to find the number of beautiful vertices. A vertex is beautiful if removing it will disconnect the graph, i.e., increase the number of connected components.

For Example:

You are given ‘N’ = 5, ‘M’ = 5 and ‘EDGES’ = [[1, 2], [1, 3], [3, 4], [3, 5], [4, 5]].

The beautiful vertices in the given graph are ‘1’ and ‘3’. If we remove ‘1’, vertex ‘2’ will be disconnected from the connected component (‘3’↔’4’↔’5’). If we remove vertex ‘3’, we will get two disjoint connected components (‘1’↔’2’) and (‘4’↔’5’).

Input Format :

The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, representing the numbers of vertices and edges, respectively.

The next line ‘M’ lines contain two space-separated integers representing an edge.

Output Format:

For each test case, print the number of beautiful vertices.

Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 2000
1 <= M <= N*(N-1)/2
1 <= EDGES[i][0] <= N
1 <= EDGES[i][1] <= N

Time Limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we will run a depth-first search from the starting node and keep track of the following information:

Discovery time of each vertex or the depth of each vertex in the DFS tree once it gets visited.
Lowpoint of each vertex. The lowpoint of any vertex ‘V’ is the lowest depth of neighbors of all descendants of ‘V’(including ‘V’ itself) in the DFS tree. We will compute the lowpoint of ‘V’ after visiting all descendants of ‘V’. The lowpoint of ‘V’ will be the minimum depth of ‘V’, the depth of all neighbors of ‘V’, and the lowpoint of all children of ‘V’ in the DFS tree.

Note: DFS tree is the pattern we get when we perform a depth-search search on the graph.

Now, a vertex is a beautiful vertex if any of the following conditions is true:

The vertex ‘V’ is a non-root vertex(have some parent ‘P’), and there is a child ‘C’ of ‘V’ such that lowpoint(‘C’) is greater than or equal to depth(‘V’).
The vertex ‘V’ is a root vertex(have no parent), the and ‘V’ has more than one child. This means that ‘V’ can build one component from each child subtree of the root(including the root).

Arrays/Lists used:

‘ANS’: To store the beautiful vertices.
‘ADJ’: To store adjacency list representation of the graph.
‘LOW’: To store lowpoint of each vertex.
‘TIN’: To store the discovery time of each vertex.
‘VIS’: To keep track of visited nodes.

Algorithm :

Initialize a list ‘ANS’ to store all the beautiful vertices.
Initialize an adjacency list ‘ADJ’ to store the given graph.
Initialize lists ‘LOW’, ‘TIN’ and a variable ‘TIMER’.
Create a graph from the given ‘EDGES’ and store it in ‘ADJ’.
Iterate ‘I’ in 0 to ‘N’
- If the ‘I’th node is not visited, call DFS on the ‘I’th node.
Return ‘ANS.SIZE’.

Maintain a function DFS(int ‘NODE’, int ‘PARENT’, list<list> ‘ADJ’, int[] ‘LOW’, int[] ‘TIN’, boolean[] ‘VIS’, list ‘ANS’)

Set ‘VIS’[‘NODE’] as true.
Set ‘LOW’[‘NODE’] and ‘TIN’[‘NODE’] as ‘TIMER’ and increment ‘TIMER’ by 1.
Initialize a variable ‘CHILD’.
Iterate ‘X’ in ‘ADJ’[‘NODE’]:
- If ‘X’ is not already visited:
  - Call DFS on ‘X’.
  - Set ‘LOW’[‘NODE’] as the minimum of ‘LOW’[‘NODE’] and ‘LOW’[‘X].
  - If ‘LOW’[‘X] is greater than or equal to ‘TIN’[‘NODE’] and ‘PARENT’ is not equal to -1:
    - If ‘ANS’ does not contain ‘NODE’:
      - Add ‘NODE’ to ‘ANS’
- Otherwise, if ‘PARENT’ is not equal to ‘X’:
  - Set ‘LOW’[‘NODE’] as the minimum of ‘LOW’[‘NODE’] and ‘TIN’[‘X].
If ‘PARENT’ is equal to -1 and ‘CHILD’ is greater than 1:
- Add ‘NODE’ to ‘ANS’.

Solve now