Graph Connectivity Queries.
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:-

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

Question

Graph Connectivity Queries.

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.

Accepted Answer

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

Space Complexity: O(n^2)Explanation:

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

Time Complexity: OtherExplanation:

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.

Java (SE 1.8)

/*

    Time Complexity: O(N * N * log(max(X,Y)))

    Space Complexity: O(N * N)

    

    Where N is the total number of nodes, 

	X and Y are value of nodes.

*/



import java.util.ArrayList;

import java.util.LinkedList;

import java.util.Queue;



public class Solution {

    

   public static int findGCD(int a, int b) {   

        if (b == 0) {

    		return a;                 

        }

        

    	return findGCD(b, a % b);   

    }

    

	public static ArrayList isConnected(int n, int thresholdValue, ArrayList> query, int q) {

        ArrayList[] adj = new ArrayList[n + 1];

        // Initializing.

        for (int i = 0; i <= n; i++) {

            adj[i] = new ArrayList();

        }

        

        for (int i = 1; i <= n; i++) {

            for (int j = i + 1; j <= n; j++) {

                if (findGCD(i,j) >= thresholdValue) {

                    adj[i].add(j);

                	adj[j].add(i);

                  }

              }

        }

        

        Boolean vis[] = new Boolean[n + 1];

        for(int i = 0; i <= n;i++)

        {

            vis[i] = false;

        }

  		int comp[] = new int[n + 1];

  		int ctr = 0;



        for (int i = 1; i <= n; i++) {

            if (vis[i] == false) {

                ctr++;

                Queue qu = new LinkedList<>();

                qu.add(i);

                vis[i] = true;



                while (!qu.isEmpty()) {

                    int u = qu.poll();

                    comp[u] = ctr;



                    for (int adjacentNode: adj[u]) {

                        if (vis[adjacentNode] == false) {

                            vis[adjacentNode] = true;

                            qu.add(adjacentNode);

                        }

                    }

                }

            }

        }



        ArrayList ans = new ArrayList();



        for (int i = 0; i < q; i++) {

            if (comp[query.get(i).get(0)] == comp[query.get(i).get(1)]) {

                ans.add(1);

            }

            else {

                ans.add(0);                                       

            }

          }

          return ans;

        

    }

}

Python (3.5)

'''

    Time Complexity: O(N * N * log(max(X,Y)))

    Space Complexity: O(N * N)

    

    Where N is the total number of nodes, 

	X and Y are value of nodes.

'''



from math import gcd

from queue import Queue



def isConnected(n,  thresholdValue,  query,  q):

    adj = []

    for i in range(n+1):

        temp = []

        adj.append(temp)



    for i in range(1, n+1):

        for j in range(i+1, n+1):

            if (gcd(i, j) >= thresholdValue):

                adj[i].append(j)

                adj[j].append(i)



    vis = [False]*(n+1)

    comp = [0]*(n+1)

    ctr = 0



    for i in range(1, n+1):

        if (vis[i] == False):

            ctr += 1

            qu = Queue(maxsize=10**5)



            qu.put(i)

            vis[i] = True



            while (not qu.empty()):

                u = qu.get()

                comp[u] = ctr



                for adjacentNode in adj[u]:

                    if(vis[adjacentNode] == False):

                        vis[adjacentNode] = True



                        qu.put(adjacentNode)



    ans = []



    for i in range(q):

        if(comp[query[i][0]] == comp[query[i][1]]):

            ans.append(1)

        else:

            ans.append(0)



    return ans

C++ (g++ 5.4)

/*

    Time Complexity: O(N * N * log(max(X,Y)))

    Space Complexity: O(N * N)

    

    Where N is the total number of nodes, 

	X and Y are value of nodes.

*/



vector  isConnected(int n, int thresholdValue, vector < pair < int, int > > query, int q) 

{

    vector  adj[n + 1];



    for (int i = 1; i <= n; i++) 

    {

        for (int j = i + 1; j <= n; j++) 

        {

            if (__gcd(i, j) >= thresholdValue) 

            {

                adj[i].push_back(j);

                adj[j].push_back(i);

            }

        }

    }



    vector  vis(n + 1, false);

    vector  comp(n + 1);

    int ctr = 0;



    for (int i = 1; i <= n; i++) 

    {

        if (vis[i] == false) 

        {

            ctr++;

            queue < int > qu;

            qu.push(i);

            vis[i] = true;



            while (!qu.empty()) 

            {

                int u = qu.front();

                qu.pop();

                comp[u] = ctr;



                for (int adjacentNode: adj[u]) 

                {

                    if (vis[adjacentNode] == false) 

                    {

                        vis[adjacentNode] = true;

                        qu.push(adjacentNode);

                    }

                }

            }

        }

    }



    vector  ans;



    for (int i = 0; i < q; i++) 

    {

        if (comp[query[i].first] == comp[query[i].second]) 

        {

            ans.push_back(1);

        }

        else 

        {

            ans.push_back(0);

        }

    }



    return ans;

}

Accepted Answer

Disjoint Set Union 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’.

Space Complexity: OtherExplanation:

O(N + Q), where ‘N’ denotes the number of nodes in the graph and Q denotes the number of queries.

We build two auxiliary arrays/lists ‘PARENT’ and ‘S’ of size ‘N’. We are also storing ‘ans’ in a list of size ‘Q’.