Skip to main content

Minimum Spanning Tree - Kruskal

Problem Statement:


Given an undirected weighted connected graph, it is required to find the Really Special SubTree in it. The Really Special SubTree is defined as a subgraph consisting of all the nodes in the graph and
  • There is only one exclusive path from a node to every other node.
  • The subgraph is of minimum overall weight (sum of all edges) among all such subgraphs.
  • While creating the Really Special SubTree, start by picking the edge with smallest weight. If there are edges of equal weight available at an instant, then the edge to be chosen first among them is the one with minimum value of sum of the following expression :
    • u + wt + v , where u and v are the node numbers of the corresponding edge and wt is the weight.
  • Even then if there is a collision, choose any one of them.
  • While doing the above, ensure that no cycle is formed while picking up edges.
Finally, you need to print the overall weight of the Tree so formed using above rules.

Code:


import java.io.*;
import java.util.*;
public class Solution {
   static class Edge implements Comparable<Edge>
       {
       int u;
       int v;
       int w;
       Edge(int u,int v,int w)
           {
           this.u=u;
           this.v=v;
           this.w=w;
           }
       public int compareTo(Edge e)
           {
           return this.w-e.w;
       }
   }
   public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
       int n=sc.nextInt();
       int m=sc.nextInt();
       ArrayList <Edge> h=new ArrayList<Edge>();
       for(int i=0;i<m;i++)
           {
           int u=sc.nextInt();
           int v=sc.nextInt();
           int w=sc.nextInt();
           Edge e=new Edge(u,v,w);
           h.add(e);
       }
       Collections.sort(h);//Sorted according the weight
       Set <Integer> s[]=new HashSet[n+1];// to maintain disjoint sets
       for(int i=0;i<n+1;i++)
           {
           s[i]=new HashSet<Integer>();
           s[i].add(i);
       }
       int len=h.size();
       long total=0;
       int count=0;
       for(int i=0;i<len;i++)
           {
           if(count==n-1){break;}// if found n-1 the edges break
           Edge e=h.get(i);         
                if((i+1)<=(len-1) && (e.w==h.get(i+1).w)){
               Edge e2= h.get(i+1);
               if((e.u+e.v+e.w)>=(e2.u+e2.v+e2.w))
                   {
                   h.set(i,e2);
                   h.set(i+1,e);
               } 
           }
           e=h.get(i);
           if(!(s[e.u].contains(e.v)) && !(s[e.v].contains(e.u)) )// if belong to different set then no cycle
               {
           total=total+e.w;
               s[e.u].addAll(s[e.v]);
               s[e.v].addAll(s[e.u]);
               count++;
                    }
       } 
   System.out.println(total);
   }

}

Comments

Post a Comment

Popular posts from this blog

A Very Basic yet important question in a life of a software developer

 Processes Vs Threads Process:  It is an execution unit where a program runs. The OS helps to create, schedule, and terminates the processes which is used by CPU. The other processes created by the main process are called child process. A process operations can be controlled with the help of PCB(Process Control Block). PCB contains all the crucial information related to processing like process id, priority, state, and contents CPU register, etc. Important properties of the process: - Creation of each process requires separate system calls for each process. - It is an isolated execution entity and does not share data and information. - Processes use the IPC(Inter-Process Communication) mechanism for communication that significantly increases the number of system calls. - Process management takes more system calls. - A process has its stack, heap memory, and data map. Thread:   A process can have multiple threads, all executing at the same time. A thread is lightw...
Post a Comment
Read more

Count the Reversals

Problem Statement: Given a string  S  consisting only of opening and closing curly brackets  '{'  and  '}'  find out the minimum number of reversals required to make a balanced expression. Input The first line of input contains an integer  T  denoting the number of test cases. Then  T  test cases follow.  The first line of each test case contains a string  S  consisting only of  {  and  } . Output Print out minimum reversals required to make  S  balanced.If it cannot be balanced, then print  -1 . Constraints 1 <=  T  <= 100 0 <    S   <= 50 Examples   Input 4 }{{}}{{{ {{}}}} {{}{{{}{{}}{{ {{{{}}}} Output 3 1 -1 0 Expected Complexity Time :   O(n) Space : O(n) Code: import java.util.*; import java.lang.*; import java.io.*; class GFG { public static void main (String[] args) { Scanner sc=new Scanner(S...
Post a Comment
Read more

CheatSheet for Searching Algorithms

CheatSheet for Searching Algorithms 1. Linear Search int search(int arr[], int x) { int n = arr.length; for(int i = 0; i < n; i++) { if(arr[i] == x) return i; } return -1; } The time complexity of above algorithm is O(n). 2. Binary Search // Returns location of key, or -1 if not found // Returns location of key, or -1 if not found int BinarySearch(int A[], int l, int r, int key) { int m; while( l <= r ) { m = l + (r-l)/2; if( A[m] == key ) // first comparison return m; if( A[m] < key ) // second comparison l = m + 1; else r = m - 1; } return -1; } The time complexity of Binary Search Theta(log(n)) Auxiliary Space: O(1) in case of iterative implementation. In case of recursive implementation, O(Logn) recursion call stack space. 3. The Ubiquitous Binary Search // Invariant: A[l] <= key and A[r] > key // Boundar...
Post a Comment
Read more