Minimize count of connections using Minimum Spanning Tree
The idea is to use a concept similar to that of Minimum Spanning Tree, as in a Graph with N nodes, only N β 1 edges are required to make all the nodes connected.
Redundant edges = Total edges β [(Number of Nodes β 1) β (Number of components β 1)]
If Redundant edges > (Number of components β 1) : It is clear that there are enough wires that can be used to connect disconnected computers.Otherwise, print -1.
Follow the steps below to solve the problem:
- Initialize an unordered map, say adj to store the adjacency list from the given information about edges.
- Initialize a vector of boolean datatype, say visited, to store whether a node is visited or not.
- Generate the adjacency list and also calculate the number of edges.
- Initialize a variable, say components, to store the count of connected components.
- Traverse the nodes of the graph using DFS to count the number of connected components and store it in the variable components.
- Initialize a variable, say redundant, and store the number of redundant edges using the above formula.
- If redundant edges > components β 1, then the minimum number of required operations is equal to components β 1. Otherwise, print -1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to visit the nodes of a graph void DFS(unordered_map< int , vector< int > >& adj, int node, vector< bool >& visited) { // If current node is already visited if (visited[node]) return ; // If current node is not visited visited[node] = true ; // Recurse for neighbouring nodes for ( auto x : adj[node]) { // If the node is not visited if (visited[x] == false ) DFS(adj, x, visited); } } // Utility function to check if it is // possible to connect all computers or not int makeConnectedUtil( int N, int connections[][2], int M) { // Stores whether a // node is visited or not vector< bool > visited(N, false ); // Build the adjacency list unordered_map< int , vector< int > > adj; // Stores count of edges int edges = 0; // Building adjacency list // from the given edges for ( int i = 0; i < M; ++i) { // Add edges adj[connections[i][0]].push_back(connections[i][1]); adj[connections[i][1]].push_back(connections[i][0]); // Increment count of edges edges += 1; } // Stores count of components int components = 0; for ( int i = 0; i < N; ++i) { // If node is not visited if (visited[i] == false ) { // Increment components components += 1; // Perform DFS DFS(adj, i, visited); } } // At least N - 1 edges are required if (edges < N - 1) return -1; // Count redundant edges int redundant = edges - ((N - 1) - (components - 1)); // Check if components can be // rearranged using redundant edges if (redundant >= (components - 1)) return components - 1; return -1; } // Function to check if it is possible // to connect all the computers or not void makeConnected( int N, int connections[][2], int M) { // Stores counmt of minimum // operations required int minOps = makeConnectedUtil(N, connections, M); // Print the minimum number // of operations required cout << minOps; } // Driver Code int main() { // Given number of computers int N = 4; // Given set of connections int connections[][2] = { { 0, 1 }, { 0, 2 }, { 1, 2 } }; int M = sizeof (connections) / sizeof (connections[0]); // Function call to check if it is // possible to connect all computers or not makeConnected(N, connections, M); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to visit the nodes of a graph public static void DFS(HashMap<Integer, ArrayList<Integer> > adj, int node, boolean visited[]) { // If current node is already visited if (visited[node]) return ; // If current node is not visited visited[node] = true ; // Recurse for neighbouring nodes for ( int x : adj.get(node)) { // If the node is not visited if (visited[x] == false ) DFS(adj, x, visited); } } // Utility function to check if it is // possible to connect all computers or not public static int makeConnectedUtil( int N, int connections[][], int M) { // Stores whether a // node is visited or not boolean visited[] = new boolean [N]; // Build the adjacency list HashMap<Integer, ArrayList<Integer> > adj = new HashMap<>(); // Initialize the adjacency list for ( int i = 0 ; i < N; i++) { adj.put(i, new ArrayList<Integer>()); } // Stores count of edges int edges = 0 ; // Building adjacency list // from the given edges for ( int i = 0 ; i < M; ++i) { // Get neighbours list ArrayList<Integer> l1 = adj.get(connections[i][ 0 ]); ArrayList<Integer> l2 = adj.get(connections[i][ 0 ]); // Add edges l1.add(connections[i][ 1 ]); l2.add(connections[i][ 0 ]); // Increment count of edges edges += 1 ; } // Stores count of components int components = 0 ; for ( int i = 0 ; i < N; ++i) { // If node is not visited if (visited[i] == false ) { // Increment components components += 1 ; // Perform DFS DFS(adj, i, visited); } } // At least N - 1 edges are required if (edges < N - 1 ) return - 1 ; // Count redundant edges int redundant = edges - ((N - 1 ) - (components - 1 )); // Check if components can be // rearranged using redundant edges if (redundant >= (components - 1 )) return components - 1 ; return - 1 ; } // Function to check if it is possible // to connect all the computers or not public static void makeConnected( int N, int connections[][], int M) { // Stores counmt of minimum // operations required int minOps = makeConnectedUtil(N, connections, M); // Print the minimum number // of operations required System.out.println(minOps); } // Driver Code public static void main(String[] args) { // Given number of computers int N = 4 ; // Given set of connections int connections[][] = { { 0 , 1 }, { 0 , 2 }, { 1 , 2 } }; int M = connections.length; // Function call to check if it is // possible to connect all computers or not makeConnected(N, connections, M); } } // This code is contributed by kingash. |
Python3
# Python3 code for the above approach # Function to visit the nodes of a graph def DFS(adj, node, visited): # If current node is already visited if (visited[node]): return # If current node is not visited visited[node] = True # Recurse for neighbouring nodes if (node in adj): for x in adj[node]: # If the node is not visited if (visited[x] = = False ): DFS(adj, x, visited) # Utility function to check if it is # possible to connect all computers or not def makeConnectedUtil(N, connections, M): # Stores whether a # node is visited or not visited = [ False for i in range (N)] # Build the adjacency list adj = {} # Stores count of edges edges = 0 # Building adjacency list # from the given edges for i in range (M): # Add edges if (connections[i][ 0 ] in adj): adj[connections[i][ 0 ]].append( connections[i][ 1 ]) else : adj[connections[i][ 0 ]] = [] if (connections[i][ 1 ] in adj): adj[connections[i][ 1 ]].append( connections[i][ 0 ]) else : adj[connections[i][ 1 ]] = [] # Increment count of edges edges + = 1 # Stores count of components components = 0 for i in range (N): # If node is not visited if (visited[i] = = False ): # Increment components components + = 1 # Perform DFS DFS(adj, i, visited) # At least N - 1 edges are required if (edges < N - 1 ): return - 1 # Count redundant edges redundant = edges - ((N - 1 ) - (components - 1 )) # Check if components can be # rearranged using redundant edges if (redundant > = (components - 1 )): return components - 1 return - 1 # Function to check if it is possible # to connect all the computers or not def makeConnected(N, connections, M): # Stores counmt of minimum # operations required minOps = makeConnectedUtil(N, connections, M) # Print the minimum number # of operations required print (minOps) # Driver Code if __name__ = = '__main__' : # Given number of computers N = 4 # Given set of connections connections = [[ 0 , 1 ], [ 0 , 2 ], [ 1 , 2 ]] M = len (connections) # Function call to check if it is # possible to connect all computers or not makeConnected(N, connections, M) # This code is contributed by ipg2016107 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to visit the nodes of a graph public static void DFS(Dictionary< int , List< int > > adj, int node, bool [] visited) { // If current node is already visited if (visited[node]) return ; // If current node is not visited visited[node] = true ; // Recurse for neighbouring nodes foreach ( int x in adj[node]) { // If the node is not visited if (visited[x] == false ) DFS(adj, x, visited); } } // Utility function to check if it is // possible to connect all computers or not public static int makeConnectedUtil( int N, int [, ] connections, int M) { // Stores whether a // node is visited or not bool [] visited = new bool [N]; // Build the adjacency list Dictionary< int , List< int > > adj = new Dictionary< int , List< int > >(); // Initialize the adjacency list for ( int i = 0; i < N; i++) { adj[i] = new List< int >(); } // Stores count of edges int edges = 0; // Building adjacency list // from the given edges for ( int i = 0; i < M; ++i) { // Get neighbours list List< int > l1 = adj[connections[i, 0]]; List< int > l2 = adj[connections[i, 0]]; // Add edges l1.Add(connections[i, 1]); l2.Add(connections[i, 0]); // Increment count of edges edges += 1; } // Stores count of components int components = 0; for ( int i = 0; i < N; ++i) { // If node is not visited if (visited[i] == false ) { // Increment components components += 1; // Perform DFS DFS(adj, i, visited); } } // At least N - 1 edges are required if (edges < N - 1) return -1; // Count redundant edges int redundant = edges - ((N - 1) - (components - 1)); // Check if components can be // rearranged using redundant edges if (redundant >= (components - 1)) return components - 1; return -1; } // Function to check if it is possible // to connect all the computers or not public static void makeConnected( int N, int [, ] connections, int M) { // Stores counmt of minimum // operations required int minOps = makeConnectedUtil(N, connections, M); // Print the minimum number // of operations required Console.WriteLine(minOps); } static void Main() { // Given number of computers int N = 4; // Given set of connections int [, ] connections = { { 0, 1 }, { 0, 2 }, { 1, 2 } }; int M = connections.GetLength(0); // Function call to check if it is // possible to connect all computers or not makeConnected(N, connections, M); } } // This code is contributed by decode2207. |
Javascript
<script> // Javascript program for the above approach // Function to visit the nodes of a graph function DFS(adj, node, visited) { // If current node is already visited if (visited[node]) return ; // If current node is not visited visited[node] = true ; // Recurse for neighbouring nodes for (let x = 0; x < adj[node].length; x++) { // If the node is not visited if (visited[adj[node][x]] == false ) DFS(adj, adj[node][x], visited); } } // Utility function to check if it is // possible to connect all computers or not function makeConnectedUtil(N, connections, M) { // Stores whether a // node is visited or not let visited = new Array(N); visited.fill( false ); // Build the adjacency list let adj = new Map(); // Initialize the adjacency list for (let i = 0; i < N; i++) { adj[i] = []; } // Stores count of edges let edges = 0; // Building adjacency list // from the given edges for (let i = 0; i < M; ++i) { // Get neighbours list let l1 = adj[connections[i][0]]; let l2 = adj[connections[i][0]]; // Add edges l1.push(connections[i][1]); l2.push(connections[i][0]); // Increment count of edges edges += 1; } // Stores count of components let components = 0; for (let i = 0; i < N; ++i) { // If node is not visited if (visited[i] == false ) { // Increment components components += 1; // Perform DFS DFS(adj, i, visited); } } // At least N - 1 edges are required if (edges < N - 1) return -1; // Count redundant edges let redundant = edges - ((N - 1) - (components - 1)); // Check if components can be // rearranged using redundant edges if (redundant >= (components - 1)) return components - 1; return -1; } // Function to check if it is possible // to connect all the computers or not function makeConnected(N, connections, M) { // Stores counmt of minimum // operations required let minOps = makeConnectedUtil(N, connections, M); // Print the minimum number // of operations required document.write(minOps); } // Given number of computers let N = 4; // Given set of connections let connections = [ [0, 1], [0, 2], [1, 2] ]; let M = connections.length; // Function call to check if it is // possible to connect all computers or not makeConnected(N, connections, M); // This code is contributed by sureh07. </script> |
1
Time Complexity: O(N + M)
Auxiliary Space: O(N)
Minimize count of connections required to be rearranged to make all the computers connected
Given an integer N, denoting the number of computers connected by cables forming a network and a 2D array connections[][], with each row (i, j) representing a connection between ith and jth computer, the task is to connect all the computers either directly or indirectly by removing any of the given connections and connecting two disconnected computers If itβs not possible to connect all the computers, print -1. Otherwise, print the minimum number of such operations required.
Examples:
Input: N = 4, connections[][] = {{0, 1}, {0, 2}, {1, 2}}
Output: 1
Explanation: Remove the connection between computers 1 and 2 and connect the computers 1 and 3.Input: N = 5, connections[][] = {{0, 1}, {0, 2}, {3, 4}, {2, 3}}
Output: 0