Last Updated: 5 Apr, 2021

Graph Connectivity Queries.

Moderate

Asked in companies

Solve now

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.

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.

Solve now

Approaches

01 Approach

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

Solve now

02 Approach

We will iterate over all the possible pairs of nodes and check if they are directly connected. We will build the graph using the disjoint set union. If two nodes in the query are part of the same root insert ‘1’ otherwise ‘0’ in the vector/list ‘ans’.

We will apply the algorithm as follows:-

Declare a list of ‘parent’ and ‘s’ of size ‘n’+1.
In Disjoint Set Union there are two main functions i.e dsunion() and root():-
- root() - Recursively determine the topmost parent of a given vertex.
- dsunion() - Connects two vertices by an edge.
Iterate ‘i’ from ‘1’ to ‘n’:-
- Initialize ‘parent[i]’ with ‘i’ and ‘s’ with ‘1’.
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 we will connect these two vertices using ‘dsunion(i,j)’.
Iterate over all the queries:-
- If ‘root(u[i])’ == ‘root(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’.

Solve now