Finding Astronauts from different countries | Java program for the above approach ; Function to perform the DFS Traversal to find the count of connected components ; Function to perform the DFS Traversal to find the count of connected components ; Marking vertex visited ; DFS call to neighbour vertices ; If the current node is not visited , then recursively call DFS ; Function to find the number of ways to choose two astronauts from the different countries ; Stores the Adjacency list ; Constructing the graph ; Stores the visited vertices ; Stores the size of every connected components ; DFS call to the graph ; Store size of every connected component ; Stores the total number of ways to count the pairs ; Traverse the array ; Print the value of ans ; Driver Code
import java . util . * ; public class GFG { static Vector < Vector < Integer > > adj ; static boolean [ ] visited ; static int num ; static void dfs ( int v ) { visited [ v ] = true ; num ++ ; for ( int i = 0 ; i < adj . get ( v ) . size ( ) ; i ++ ) { if ( ! visited [ adj . get ( v ) . get ( i ) ] ) { dfs ( adj . get ( v ) . get ( i ) ) ; } } } static void numberOfPairs ( int N , int [ ] [ ] arr ) { adj = new Vector < Vector < Integer > > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { adj . add ( new Vector < Integer > ( ) ) ; } for ( int i = 0 ; i < 2 ; i ++ ) { adj . get ( arr [ i ] [ 0 ] ) . add ( arr [ i ] [ 1 ] ) ; adj . get ( arr [ i ] [ 1 ] ) . add ( arr [ i ] [ 0 ] ) ; } visited = new boolean [ N ] ; Arrays . fill ( visited , false ) ; Vector < Integer > v = new Vector < Integer > ( ) ; num = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( ! visited [ i ] ) { dfs ( i ) ; v . add ( num ) ; num = 0 ; } } int ans = N * ( N - 1 ) / 2 + 1 ; for ( int i = 0 ; i < v . size ( ) ; i ++ ) { ans -= ( v . get ( i ) * ( v . get ( i ) - 1 ) / 2 ) + 1 ; } System . out . print ( ans ) ; } public static void main ( String [ ] args ) { int N = 6 ; int [ ] [ ] arr = { { 0 , 1 } , { 0 , 2 } , { 2 , 5 } } ; numberOfPairs ( N , arr ) ; } }