Smallest vertex in the connected components of all the vertices in given undirect graph
Given an undirected graph G(V, E) consisting of2 N vertices and M edges, the task is to find the smallest vertex in the connected component of the vertex i for all values of i in the range [1, N].
Examples:
Input: N = 5, edges[] = {{1, 2}, {2, 3}, {4, 5}}
Output: 1 1 1 4 4
Explanation: The given graph can be divided into a set of two connected components, i.e, {1, 2, 3} and {4, 5}.
- For i = 1, vertex 1 belongs to the component {1, 2, 3}. Therefore, the minimum vertex in the set is 1.
- For i = 2, vertex 2 belongs to the component {1, 2, 3}. Therefore, the minimum vertex in the set is 1.
- For i = 3, vertex 3 belongs to the component {1, 2, 3}. Therefore, the minimum vertex in the set is 1.
- For i = 4, vertex 4 belongs to the component {4, 5}. Therefore, the minimum vertex in the set is 4.
- For i = 5, vertex 5 belongs to the component {4, 5}. Therefore, the minimum vertex in the set is 4.
Input: N = 6, edges[] = {{1, 3}, {2, 4}}
Output: 1 2 1 2 5 6
Approach: The given problem can be solved efficiently with the help of Disjoint Set Union. It can be observed that the vertices connected by an edge can be united into the same set and an unordered map can be used to keep track of the smallest vertex of each of the formed sets. Below are the steps to follow:
- Implement the find_set and union_set function of the Disjoint Set Union using the approach discussed in this article where find_set(x) returns the set number containing x, and union_set(x, y) unites the set containing x with the set containing y.
- Traverse the given array edges[] and for each edge (u, v), unite the set containing u with the set containing v.
- Create an unordered map minVal, where minVal[x] stores the minimum vertex of the set containing x as an element.
- Iterate over all vertices using a variable i and for each vertex set the value of minVal[find_set(node i)] to the minimum of minVal[find_set(i)] and i.
- After completing the above steps, for each vertex, i in the range [1, N], print the value of minVal[find_set(i)] as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; const int maxn = 100; // Stores the parent and size of the // set of the ith element int parent[maxn], Size[maxn]; // Function to initialize the ith set void make_set( int v) { parent[v] = v; Size[v] = 1; } // Function to find set of ith vertex int find_set( int v) { // Base Case if (v == parent[v]) { return v; } // Recursive call to find set return parent[v] = find_set( parent[v]); } // Function to unite the set that includes // a and the set that includes b void union_sets( int a, int b) { a = find_set(a); b = find_set(b); // If a and b are not from same set if (a != b) { if (Size[a] < Size[b]) swap(a, b); parent[b] = a; Size[a] += Size[b]; } } // Function to find the smallest vertex in // the connected component of the ith // vertex for all i in range [1, N] void findMinVertex( int N, vector<pair< int , int > > edges) { // Loop to initialize the ith set for ( int i = 1; i <= N; i++) { make_set(i); } // Loop to unite all vertices connected // by edges into the same set for ( int i = 0; i < edges.size(); i++) { union_sets(edges[i].first, edges[i].second); } // Stores the minimum vertex value // for ith set unordered_map< int , int > minVal; // Loop to iterate over all vertices for ( int i = 1; i <= N; i++) { // If current vertex does not exist // in minVal initialize it with i if (minVal[find_set(i)] == 0) { minVal[find_set(i)] = i; } // Update the minimum value of // the set having the ith vertex else { minVal[find_set(i)] = min(minVal[find_set(i)], i); } } // Loop to print required answer for ( int i = 1; i <= N; i++) { cout << minVal[find_set(i)] << " " ; } } // Driver Code int main() { int N = 6; vector<pair< int , int > > edges = { { 1, 3 }, { 2, 4 } }; findMinVertex(N, edges); return 0; } |
Java
// Java program for the above approach import java.util.*; public class Main { // Stores the parent and size of the // set of the ith element static int [] parent = new int [ 100 ]; static int [] Size = new int [ 100 ]; // Function to initialize the ith set static void make_set( int v) { parent[v] = v; Size[v] = 1 ; } // Function to find set of ith vertex static int find_set( int v) { // Base Case if (v == parent[v]) { return v; } // Recursive call to find set return parent[v] = find_set(parent[v]); } // Function to unite the set that includes // a and the set that includes b static void union_sets( int a, int b) { a = find_set(a); b = find_set(b); // If a and b are not from same set if (a != b) { if (Size[a] < Size[b]) { int temp = a; a = b; b = temp; } parent[b] = a; Size[a] += Size[b]; } } // Function to find the smallest vertex in // the connected component of the ith // vertex for all i in range [1, N] static void findMinVertex( int N, ArrayList<ArrayList<Integer> > edges) { // Loop to initialize the ith set for ( int i = 1 ; i <= N; i++) { make_set(i); } // Loop to unite all vertices connected // by edges into the same set for ( int i = 0 ; i < edges.size(); i++) { union_sets(edges.get(i).get( 0 ), edges.get(i).get( 1 )); } // Stores the minimum vertex value // for ith set Map<Integer, Integer> minVal = new HashMap<>(); // Loop to iterate over all vertices for ( int i = 1 ; i <= N; i++) { // If current vertex does not exist // in minVal initialize it with i if (!minVal.containsKey(find_set(i))) { minVal.put(find_set(i), i); } // Update the minimum value of // the set having the ith vertex else { minVal.put( find_set(i), Math.min(( int )minVal.getOrDefault( (Integer)find_set(i), 0 ), i)); } } // Loop to print required answer for ( int i = 1 ; i <= N; i++) { System.out.print(minVal.get(find_set(i)) + " " ); } } // Driver Code public static void main(String[] args) { int N = 6 ; ArrayList<ArrayList<Integer> > edges = new ArrayList<ArrayList<Integer> >(); ArrayList<Integer> a1 = new ArrayList<Integer>(); a1.add( 1 ); a1.add( 3 ); edges.add(a1); ArrayList<Integer> a2 = new ArrayList<Integer>(); a2.add( 2 ); a2.add( 4 ); edges.add(a2); findMinVertex(N, edges); } } // This code is contributed by Tapesh(tapeshdua420) |
Python3
# Python 3 program for the above approach maxn = 100 # Stores the parent and size of the # set of the ith element parent = [ 0 ] * maxn Size = [ 0 ] * maxn # Function to initialize the ith set def make_set(v): parent[v] = v Size[v] = 1 # Function to find set of ith vertex def find_set(v): # Base Case if (v = = parent[v]): return v # Recursive call to find set parent[v] = find_set( parent[v]) return parent[v] # Function to unite the set that includes # a and the set that includes b def union_sets(a, b): a = find_set(a) b = find_set(b) # If a and b are not from same set if (a ! = b): if (Size[a] < Size[b]): a, b = b, a parent[b] = a Size[a] + = Size[b] # Function to find the smallest vertex in # the connected component of the ith # vertex for all i in range [1, N] def findMinVertex( N, edges): # Loop to initialize the ith set for i in range ( 1 , N + 1 ): make_set(i) # Loop to unite all vertices connected # by edges into the same set for i in range ( len (edges)): union_sets(edges[i][ 0 ], edges[i][ 1 ]) # Stores the minimum vertex value # for ith set minVal = {} # Loop to iterate over all vertices for i in range ( 1 , N + 1 ): # If current vertex does not exist # in minVal initialize it with i if (find_set(i) not in minVal): minVal[find_set(i)] = i # Update the minimum value of # the set having the ith vertex else : minVal[find_set(i)] = min (minVal[find_set(i)], i) # Loop to print required answer for i in range ( 1 , N + 1 ): print (minVal[find_set(i)], end = " " ) # Driver Code if __name__ = = "__main__" : N = 6 edges = [[ 1 , 3 ], [ 2 , 4 ]] findMinVertex(N, edges) # This code is contributed by ukasp. |
C#
// C# program for the above approach using System; using System.Collections.Generic; using System.Linq; class Program { // Stores the parent and size of the // set of the ith element static int [] parent = new int [100]; static int [] Size = new int [100]; // Function to initialize the ith set static void make_set( int v) { parent[v] = v; Size[v] = 1; } // Function to find set of ith vertex static int find_set( int v) { // Base Case if (v == parent[v]) { return v; } // Recursive call to find set return parent[v] = find_set(parent[v]); } // Function to unite the set that includes // a and the set that includes b static void union_sets( int a, int b) { a = find_set(a); b = find_set(b); // If a and b are not from same set if (a != b) { if (Size[a] < Size[b]) { int temp = a; a = b; b = temp; } parent[b] = a; Size[a] += Size[b]; } } // Function to find the smallest vertex in // the connected component of the ith // vertex for all i in range [1, N] static void findMinVertex( int N, List<List< int > > edges) { // Loop to initialize the ith set for ( int i = 1; i <= N; i++) { make_set(i); } // Loop to unite all vertices connected // by edges into the same set for ( int i = 0; i < edges.Count(); i++) { union_sets(edges[i][0], edges[i][1]); } // Stores the minimum vertex value // for ith set Dictionary< int , int > minVal = new Dictionary< int , int >(); // Loop to iterate over all vertices for ( int i = 1; i <= N; i++) { // If current vertex does not exist // in minVal initialize it with i if (!minVal.ContainsKey(find_set(i))) { minVal.Add(find_set(i), i); } // Update the minimum value of // the set having the ith vertex else { minVal[find_set(i)] = Math.Min( ( int )minVal.GetValueOrDefault( ( int )find_set(i), 0), i); } } // Loop to print required answer for ( int i = 1; i <= N; i++) { Console.Write( "{0} " , minVal.GetValueOrDefault( ( int )find_set(i), 0)); } } // Driver Code public static void Main() { int N = 6; List<List< int > > edges = new List<List< int > >(); List< int > a1 = new List< int >(); a1.Add(1); a1.Add(3); edges.Add(a1); List< int > a2 = new List< int >(); a2.Add(2); a2.Add(4); edges.Add(a2); findMinVertex(N, edges); } } // This code is contributed by tapeshdua420. |
Javascript
<script> // JavaScript program for the above approach const maxn = 100; // Stores the parent and size of the // set of the ith element let parent = new Array(maxn); let Size = new Array(maxn); // Function to initialize the ith set function make_set(v) { parent[v] = v; Size[v] = 1; } // Function to find set of ith vertex function find_set(v) { // Base Case if (v == parent[v]) { return v; } // Recursive call to find set return parent[v] = find_set(parent[v]); } // Function to unite the set that includes // a and the set that includes b function union_sets(a, b) { a = find_set(a); b = find_set(b); // If a and b are not from same set if (a != b) { if (Size[a] < Size[b]){ let temp = a; a = b; b = temp; } parent[b] = a; Size[a] += Size[b]; } } // Function to find the smallest vertex in // the connected component of the ith // vertex for all i in range [1, N] function findMinVertex(N,edges) { // Loop to initialize the ith set for (let i = 1; i <= N; i++) { make_set(i); } // Loop to unite all vertices connected // by edges into the same set for (let i = 0; i < edges.length; i++) { union_sets(edges[i][0],edges[i][1]); } // Stores the minimum vertex value // for ith set let minVal = new Map(); // Loop to iterate over all vertices for (let i = 1; i <= N; i++) { // If current vertex does not exist // in minVal initialize it with i if (minVal.has(find_set(i)) == false ) { minVal.set(find_set(i),i); } // Update the minimum value of // the set having the ith vertex else { minVal.set(find_set(i), Math.min(minVal.get(find_set(i)), i)); } } // Loop to print required answer for (let i = 1; i <= N; i++) { document.write(minVal.get(find_set(i)), " " ); } } // Driver Code let N = 6; let edges = [ [ 1, 3 ], [ 2, 4 ] ]; findMinVertex(N, edges); // This code is contributed by shinjanpatra </script> |
1 2 1 2 5 6
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us