Hey, the code is passing only 1 test case and giving run time error in others

#1

import java.util.*;

public class Main
{
public static void main(String [] args)
{
Scanner scn = new Scanner(System.in);

    int n = scn.nextInt();
    int m = scn.nextInt();
    
    //graph
    HashMap <Integer, HashSet<Integer>> graph = new HashMap <> ();
    
    for(int i = 0 ; i<m; i++)
    {
        int X = scn.nextInt();
        int Y = scn.nextInt();
        
        if(!graph.containsKey(X))
            graph.put(X, new HashSet <> ());
        
        graph.get(X).add(Y);
        
        
        if(!graph.containsKey(Y))
            graph.put(Y, new HashSet <> ());
        
        graph.get(Y).add(X);
        
    }
    
    
    System.out.println(getDisconnectedCities(n,graph));
}



public static int getDisconnectedCities(int n, HashMap <Integer, HashSet<Integer>> graph)
{
    
    //stores the no. of connected cities
    //present in one disconnected component
    //of the graph
    ArrayList <Integer> connectedCities = new ArrayList <> ();
    
    int finalAns = 0, ans, len = 0;
    
    HashMap <Integer,Boolean> visited = new HashMap <> ();
    
    Stack <Integer> st = new Stack <> ();
    
    
    for(int key = 0; key<n; key++)
    {
        
        if(visited.containsKey(key))
            continue;
            
        //applying dft
        
        st.push(key);
        ans = 0;
        
        while(!st.isEmpty())
        {
            int rp = st.pop();
            
            if(visited.containsKey(rp))
                continue;
                
            visited.put(rp,true);
            
            //no. of connected cities
            //present in the current
            //component
            ans++;
            
            for(Integer nbr : graph.get(rp))
            {
                if(!visited.containsKey(nbr))
                {
                    st.push(nbr);
                }
            }
        }
        
        
        connectedCities.add(ans);
        len++;
        
        for(int i = len-2; i>=0; i--)
        {
           finalAns += connectedCities.get(len-1)*connectedCities.get(i);
        }
        
        
    }
    
    
    
    return finalAns;
}

}

#2

refer to this corrected code

#3

i actually corrected my code. Thank you

1 Like