Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
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 <Integer> ());
graph.get(X).add(Y);
if(!graph.containsKey(Y))
graph.put(Y, new HashSet <Integer> ());
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;
}
}