Number of Operations to Make Network Connected
MST & Disjoint Set DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Minimum Operations to Connect a Graph by Reusing Edges, Disjoint Set Union, Union by Rank, Union by Size, Path Compression, Graph, Connected Components, Edge, Time Complexity, Space Complexity, union-find, graph components, graph traversal, graph properties, time complexity analysis, DSU Applications.
Minimum Number of Operations to Make a Graph Connected Problem Statement You are given a graph with n vertices and m edges. You can remove one edge from anywhere and add that edge between any two vertices in one operation. Find the minimum number of operations that will be required to make the graph connected. If it is not possible to make the graph connected, return 1. Input Specification The input consists of: An integer N, representing the number of vertices. An integer M, representing the number of edges. A 2D array Edge[] of size Mx2, where each Edge[i] = [u, v] denotes an undirected edge between vertex u and vertex v. Output Specification Return an integer representing the minimum number of operations required to make the graph connected. If it's not possible, return 1. Constraints Sample Test Cases Example 1 Input: Output: Explanation: We need a minimum of 1 operation to make the two components connected. We can remove the edge (1,2) and add the edge between node 2 and node 3. Example 2 Input: Output: Explanation: We need a minimum of 2 operations to make the two components connected. We can remove the edge (0,2) and add the edge between node 3 and node 4 and we can remove the edge (0,3) and add it between nodes 6 and 8.