Graph Connectivity Queries.

Moderate
0/80
Average time to solve is 15m
2 upvotes
Asked in companies
VisaSnapdeal Ltd.

Problem statement

You have been given a graph consisting of ‘N’ nodes and a threshold value ‘THRESHOLDVALUE’. Two different nodes ‘X’ and ‘Y’ are directly connected to each other if and only if there exists a ‘Z’ such that all of the following are true:-

‘X’ % ‘Z’ == 0 
‘Y’ % ‘Z’ == 0
‘Z’ >= ‘THRESHOLDVALUE’

You are given ‘Q’ queries where each query consists of two distinct nodes ‘U’ and ‘V’, you must determine if ‘U’ and ‘V’ are connected directly or indirectly. Return a vector/list of size ‘Q’ where ‘i-th’ element is ‘1’ if nodes in ith query are connected directly or indirectly otherwise it is ‘0’.

Example: 
Let’s say ‘N’ is 6 and 'M' is ‘2’. Then our graph will look as follows:-

subsequence

There is an edge between ‘2’ and ‘4’, ‘4’ and ‘6’ and ‘2’ and ‘6’ because their gcd is 2 which is equal to ‘m’. There is an edge between ‘3’ and ‘6’ because their gcd is 3 which is greater than ‘m’. If the query consists of vertices ‘2’ and ‘3’ answer will be ‘1’ because they are indirectly connected.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line 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 ‘THRESHOLDVALUE’ representing the number of nodes and the threshold value.

The second line contains a single integer ‘q’ representing the number of queries.

Each of the next ‘q’ lines contains two space-separated integers representing the vertices for which you need to find if they are connected directly or indirectly.
Output Format: 
For each test case, print a single line containing space-separated integers denoting answers to all the queries. 

The output of each test case will be printed in a separate line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
1 <= N <= 100
1 <= THRESHOLDVALUE <= 100
1 <= Q <= 10000
1 <= U[i] <= N
1 <= V[i] <= N

Where ‘T’ is the number of test cases.‘N’ is the number of nodes in the graph. ‘THRESHOLDVALUE’ is the threshold value. ‘Q’ is the number of queries. ‘U[i]’ and ‘V[i]’ are vertices of the i-th query.

Time Limit: 1 sec.
Sample Input 1:
2
6 2
3
1 2
2 3
3 4
6 3
2
2 3
3 6
Sample Output 1:
0 1 1
0 1

Sample Output 1 Explanation:

Test case 1:

The graph looks as follows:-

subsequence

Nodes 1 and 2 are not connected directly or indirectly. Therefore answer to this query is 0. Nodes 2 and 3 are connected indirectly. Therefore answer to this query is 1. Nodes 3 and 4 are connected indirectly. Therefore answer to this query is 1.

Therefore the answer is [0,1,1].

Test case 2:

The graph looks as follows:-

subsequence

Nodes 2 and 3 are not connected directly or indirectly. Therefore answer to this query is 0. Nodes 3 and 6 are connected directly. Therefore answer to this query is 1.

Therefore the answer is [0,1].
Sample Input 2:
2
4 1
3
1 2
2 3
3 4
4 4
2
1 2
2 3
Sample Output 2:
1 1 1
0 0
Hint

Iterate over all possible pairs of vertices. 

Approaches (2)
Breadth First Search.

We will iterate over all the possible pairs of nodes and check if they are directly connected. We will build the graph and using a breadth-first search we can find all the connected components. If two nodes in the query are part of the same component insert ‘1’ otherwise ‘0’ in the vector/list ‘ans’.


 

We will apply the algorithm as follows:-

  • Declare a list of list/vector ‘adj’ of size ‘n’+1 where ‘adj[i]’ stores nodes that are directly connected to node ‘i’.
  • Iterate ‘i’ from ‘1’ to ‘n’:-
    • Iterate ‘j’ from ‘i+1’ to ‘n’:-
      • If ‘gcd(i,j)>=thresholdValue’ then node ‘i’ and ‘j’ are directly connected. Therefore push ‘j’ in ‘adj[i]’ and ‘i’ in ‘adj[j]’.
  • Maintain an auxiliary array ‘vis’ which maintains if ‘i-th’ node has been visited.
  • Maintain an auxiliary array ‘comp’ which stores which connected component is ‘i-th’ node part of.
  • Declare ‘ctr’ and initialize it with ‘0’
  • Iterate ‘i’ from ‘1’ to ‘n’:-
    • If node ‘i’ has not been visited yet:-
      • Mark node ‘i’ as visited and insert it in the queue.
      • Increase ‘ctr’ by ‘1’ as it is a new component.
      • Iterate till the queue is empty:-
        • Pop the front element of ‘qu’ and store it in ‘u’.
        • Initialize ‘comp[u]’ with ‘ctr’
        • Iterate over ‘adj[u]’
          • If the ‘adjacentNode’ is not visited yet. Mark ‘vis[adjacentNode]’ as true and insert ‘adjacentNode’ in queue.
  • Iterate over all the queries:-
    • If ‘comp[u[i]]’ == ‘comp[v[i]]’ then u[i] and v[i] are connected directly or indirectly therefore push ‘1’ in ‘ans’.
    • Else push ‘0’ in ‘ans’.
  • Return ‘ans’.
Time Complexity

O(N * N * log(max(X, Y)’), where ‘N’ denotes the number of nodes in the graph and X and Y denotes the value of nodes.

 

We are calculating the greatest common divisor for each pair of nodes and checking if they are directly connected by an edge.

Space Complexity

O(N * N), where ‘N’ denotes the number of nodes in the graph.


 

We build an adjacency list where ‘i-th’ vector/list can be of size ‘N’.

Code Solution
(100% EXP penalty)
Graph Connectivity Queries.
Full screen
Console