Beautiful Vertices

Hard
0/120
profile
Contributed by
4 upvotes
Asked in companies
MicrosoftUberAccolite

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’).
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5 5
1 2
1 3
3 4
3 5
4 5
3 2
1 2
2 3
Sample Output 1:
2
1
Explanation of Sample Input 1:
For the first test case, the graph will look like this:


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 connected components (‘1’↔’2’) and (‘4’↔’5’).

For the second test case, the graph will look like this:


The beautiful vertex in the given graph is ‘2’. If we remove vertex ‘2’, we will get two disjoint components (‘1’) and (‘3’).
Sample Input 2:
2
3 3
1 2
1 3
2 3
4 3
1 2
2 3
3 4
Sample Output 2:
0
2
Hint

Try to use Depth-First Search.

Approaches (1)
Depth-First Search

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’.
Time Complexity

O(N + M), where ‘N’ is the number of vertices, and 'M' is the number of edges.

 

We are just performing DFS with additional arrays and the time complexity of DFS is O(N + M). Hence, the total time complexity is O(N + M).

Space Complexity

O(N + M), where ‘N’ is the number of vertices, and 'M' is the number of edges.

 

The maximum space is taken by the adjacency list ‘ADJ’, i.e., O(N + M). Hence, the total space complexity is O(N + M).

Code Solution
(100% EXP penalty)
Beautiful Vertices
Full screen
Console