Number of operations to make Graph connected
You have been given a graph consisting of ‘N’ vertices numbered from 1 to ‘N’. The graph has ‘M’ edges. In an operation, you can shift an edge between two directly connected vertices to between pair of disconnected vertices to make them directly connected. Return the minimum number of operations to make the graph connected. If it is not possible to make graph connected return -1.

Example:

Let’s say ‘N’ is 4 and ‘M' is 3. The 3 edges are (1,2), (2,3) and (1,3). Then our graph will look as follows:-

To make the graph connected we can shift the edge between (1,3) to (1,4). This operation will make the graph connected. There are multiple ways in which we can make graph connected. So, in this case, we can make graph connected in just one operation.

Note:

1. A connected graph is a graph that is connected in the sense of a topological space, i.e., there is a path from any vertex to any other vertex in the graph. 2. There are no repeated edges and self-loops in the graph. 3. You do not need to print anything; it has already been taken care of. Just implement the function.

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 ‘M’ representing the number of vertices and the number of edges in the graph. Each of the next ‘M’ lines contains two space-separated integers representing the vertices that are directly connected by an edge.

Output Format:

For each test case, print a single line containing a single integer denoting the minimum number of operations to make the graph connected. If it is not possible to make graph connected return -1. The output of each test case will be printed in a separate line.

Note:

You do not need to input or print anything, as it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Number of operations to make Graph connected

You have been given a graph consisting of ‘N’ vertices numbered from 1 to ‘N’. The graph has ‘M’ edges. In an operation, you can shift an edge between two directly connected vertices to between pair of disconnected vertices to make them directly connected. Return the minimum number of operations to make the graph connected. If it is not possible to make graph connected return -1.

Example:

Let’s say ‘N’ is 4 and ‘M' is 3. The 3 edges are (1,2), (2,3) and (1,3). Then our graph will look as follows:-

subsequence

To make the graph connected we can shift the edge between (1,3) to (1,4). This operation will make the graph connected. There are multiple ways in which we can make graph connected. So, in this case, we can make graph connected in just one operation.

Note:

1. A connected graph is a graph that is connected in the sense of a topological space, i.e., there is a path from any vertex to any other vertex in the graph.

2. There are no repeated edges and self-loops in the graph.

3. You do not need to print anything; it has already been taken care of. Just implement the function.

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 ‘M’ representing the number of vertices and the number of edges in the graph.

Each of the next ‘M’ lines contains two space-separated integers representing the vertices that are directly connected by an edge.

Output Format:

For each test case, print a single line containing a single integer denoting the minimum number of operations to make the graph connected. If it is not possible to make graph connected return -1.

The output of each test case will be printed in a separate line.

Note:

You do not need to input or print anything, as it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10000
1 <= M <= 10000
1 <= U[i], V[i] <= N

Where ‘T’ is the number of test cases.‘N’ is the number of vertices in the graph. ‘M’ is the number of edges in the graph. ‘U[i]’ and ‘V[i]’ are vertices of the i-th edge.

Time Limit: 1sec.

Accepted Answer

Breadth First Search.

For a graph with ‘N’ vertices to be connected, there must be at least ‘N’ - 1 edges in the graph. If a graph has less than ‘N' - 1 edges it is impossible to make the graph connected. Otherwise, it is always possible to make graph connected. As we need to find the minimum number of operations to make the graph connected we will think greedily. We will find the total number of connected components in the graph. We can treat each connected component in the graph as a single vertex. Basically, we want to shift edges such that these components become connected. Therefore answer will be the total number of connected components - 1.

We will apply the algorithm as follows:-

If ‘m’ is less than ‘N’ - 1 return -1.
Declare a list of list/vector ‘adj’ of size ‘N’ + 1 where ‘adj[i]’ stores vertices that are directly connected to node ‘i’.
Iterate ‘i’ from ‘1’ to ‘m’:-
- Therefore push ‘v[i]’ in ‘adj[u[i]]’ and ‘u[i]’ in ‘adj[v[i]]’.
Maintain an auxiliary array ‘vis’ which maintains if ‘i-th’ vertex has been visited.
Declare ‘ctr’ and initialize it with ‘0’. It stores the number of connected components.
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 ‘q’ and store it in ‘u’.
    - Iterate over ‘adj[u]’
      - If the ‘adjacentNode’ is not visited yet. Mark ‘vis[adjacentNode]’ as true and insert ‘adjacentNode’ in queue.
Declare ‘ans’ and initialize it with ‘ctr’ - 1.
Return ‘ans’.

Space Complexity: OtherExplanation:

O(N + M), where N denotes the number of vertices and N denotes the number of edges in the graph.

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

Time Complexity: OtherExplanation:

O(N + M), where N denotes the number of vertices and M denotes the number of edges in the graph.

We are visiting each vertex and edge once.

C++ (g++ 5.4)

/*

    Time Complexity: O(N + M)

    Space Complexity: O(N + M)

    

    Where N is the total number of nodes and  is total number of edges

*/



int makeGraphConnected(int n, vector < pair < int, int > > edges, int m) 

{

      if (m < n - 1) 

      {

        return -1;

      }



      vector < int > adj[n + 1];

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

        adj[edges[i].first].push_back(edges[i].second);

        adj[edges[i].second].push_back(edges[i].first);

      }



      vector < bool > vis(n + 1, false);

      int ctr = 0;



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

      {

        if (vis[i] == false) 

        {

          queue < int > q;

          vis[i] = true;

          q.push(i);

          ctr++;



          while (!q.empty()) 

          {

            int u = q.front();

            q.pop();

            for (int v: adj[u]) 

            {

              if (vis[v] == false) 

              {

                vis[v] = true;

                q.push(v);

              }

            }

          }

        }

      }



      int ans = ctr - 1;



      return ans;

}

Java (SE 1.8)

/*

    Time Complexity: O(N + M)

    Space Complexity: O(N + M)

    

    Where N is the total number of nodes and M is total number of edges

*/



import java.util.ArrayList;

import java.util.LinkedList;

import java.util.Queue;



public class Solution {

    public static int makeGraphConnected(int n, ArrayList> edges, int m) {

          if (m < n - 1) {

              return -1;

          }

        

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

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

            adj[i] = new ArrayList();

        }

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

            adj[edges.get(i).get(0)].add(edges.get(i).get(1));

            adj[edges.get(i).get(1)].add(edges.get(i).get(0));

        }

        

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

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

        {

            vis[i] = false;

        }

     	int ctr = 0;



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

            if (vis[i] == false) {

                Queue q = new LinkedList<>();

                vis[i] = true;

                q.add(i);

                ctr++;



                while (!q.isEmpty()) {

                    int u = q.poll();

                    for (int v: adj[u]) {

                        if (vis[v] == false) {

                            vis[v] = true;

                            q.add(v);

                        }

                    }

                }

            }

        }

        int ans = ctr - 1;



      	return ans;

    }

}

Python (3.5)

'''

    Time Complexity: O(N + M)

    Space Complexity: O(N + M)

    

    Where N is the total number of nodes and M is total number of edges.    

'''



from queue import Queue



def makeGraphConnected( n,  edges,  m):    

    

    if (m < n - 1):

        return -1

    

    adj = []

    for i in range(n+1):

        temp = []

        adj.append(temp)

        

    

    for i in range(m):

        

        adj[edges[i][0]].append(edges[i][1])

        adj[edges[i][1]].append(edges[i][0])

  

    vis = [False]*(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()



                for adjacentNode in adj[u]:

                    if(vis[adjacentNode] == False):

                        vis[adjacentNode] = True



                        qu.put(adjacentNode)



    ans = ctr - 1

    

    return ans

Accepted Answer

Disjoint Set Union Approach

For a graph with ‘n’ vertices to be connected, there must be at least ‘N’-1 edges in the graph. If a graph has less than ‘N’-1 edges it is impossible to make the graph connected. Otherwise, it is always possible to make graph connected. As we need to find the minimum number of operations to make the graph connected we will think greedily. We will find the total number of connected components in the graph. We can treat each connected component in the graph as a single vertex. Basically, we want to shift edges such that these components become connected. Therefore answer will be the total number of connected components - 1. We can find the total number of connected components using disjoint set union.

We will apply the algorithm as follows:-

If ‘M’ is less than ‘N’-1 return -1.
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’.
Declare ‘ans’ and initialize it with ‘N’ which signifies the number of connected components in the graph. Till now no edge has been added, therefore the number of connected components is ‘N’.
Iterate ‘i’ from ‘1’ to ‘M’:-
- Check if root(u[i])!=root(v[i]) i.e. whether u[i] & v[i] are part of different connected component. If they are part of different connected component:-
  - We will connect these two vertices using ‘dsunion(u[i],v[i])’.
  - We will decrease the total number of connected components i.e. ‘ans’ by 1 because when we add connect edge between u[i] and v[i] the two components they are part of becomes a single component.
Return ‘ans’ - 1 because ‘ans’ stores the total number of connected components.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ denotes the number of vertices.

We build two auxiliary arrays/lists ‘parent’ and ‘s’ of size ‘N’.

Time Complexity: OtherExplanation:

O(N + M), where ‘N’ denotes the number of vertices and ‘M’ denotes the number of edges in the graph.

We are visiting each vertex and edge once.

Java (SE 1.8)

/*

    Time Complexity: O(N + M)

    Space Complexity: O(N)

    

    Where N is the total number of nodes and M is total number of edges

*/



import java.util.ArrayList;



public class Solution {

    static int parent[] = new int[10005];

    static int s[] = new int[10005];



    public static int root(int a) {

        if (a == parent[a]) {

            return a;

          }



          return parent[a] = root(parent[a]);

    }



    public static void dsunion(int a, int b) {

        a = root(a);

      	b = root(b);



      	if (a != b) {

            if (s[a] < s[b]){

                int temp = a;

            	a = b;

           	 	b = temp;

        	}

          	parent[b] = a;

          	s[a] += s[b];

      	}

   	}

    

    public static int makeGraphConnected(int n, ArrayList> edges, int m) {

        if (m < n - 1) {

            return -1;

        }



        int ans = n;

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

            parent[i] = i;

            s[i] = 1;

        }



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

            if (root(edges.get(i).get(0)) != root(edges.get(i).get(1))) {

                dsunion(edges.get(i).get(0), edges.get(i).get(1));

                ans--;

            }

        }



        return (ans - 1);

    }

}

Python (3.5)

'''

    Time Complexity: O(N + M)

    Space Complexity: O(N)

    

    Where N is the total number of nodes and M is total number of edges.

'''



def root(a):



    global parent

    if (a == parent[a]):

        return a



    parent[a] = root(parent[a])

    return parent[a]



def dsunion(a,  b):



    global parent, s

    a = root(a)

    b = root(b)



    if (a != b):

        if (s[a] < s[b]):

            s[a], s[b] = s[b], s[a]



        parent[b] = a

        s[a] += s[b]



def makeGraphConnected( n,  edges,  m):

    global parent, s

    

    if (m < n - 1):

        return -1

    

    ans =n

    parent = [0]*10005

    s = [0]*10005



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

        parent[i] = i

        s[i] = 1

    

    for i in range(m):

        if(root(edges[i][0])!= root(edges[i][1])):

            dsunion(edges[i][0], edges[i][1])

            ans-=1

    

    return (ans - 1)

C++ (g++ 5.4)

/*

    Time Complexity: O(N + M)

    Space Complexity: O(N)

    

    Where N is the total number of nodes and M is total number of edges

*/



int parent[10005];

int s[10005];



int root(int a) 

{

  if (a == parent[a]) 

  {

    return a;

  }



  return parent[a] = root(parent[a]);

}



void dsunion(int a, int b) 

{

  a = root(a);

  b = root(b);



  if (a != b) 

  {

    if (s[a] < s[b])

      swap(a, b);



    parent[b] = a;

    s[a] += s[b];

  }

}



int makeGraphConnected(int n, vector < pair < int, int > > edges, int m) 

{

      if (m < n - 1) 

      {

        return -1;

      }



      int ans = n;

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

      {

        parent[i] = i;

        s[i] = 1;

      }



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

        if (root(edges[i].first) != root(edges[i].second)) 

        {

          dsunion(edges[i].first, edges[i].second);

          ans--;

        }

      }



      return (ans - 1);

}

Example:

Note:

Input Format:

Output Format:

Note:

Constraints:

Top Uber Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern