Finding Astronauts from different countries | 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
let adj ; let visited ; let num ; function dfs ( v ) { visited [ v ] = true ; num ++ ; for ( let i = 0 ; i < adj [ v ] . length ; i ++ ) { if ( ! visited [ adj [ v ] [ i ] ] ) { dfs ( adj [ v ] [ i ] ) ; } } } function numberOfPairs ( N , arr ) { adj = [ ] ; for ( let i = 0 ; i < N ; i ++ ) { adj . push ( [ ] ) ; } for ( let i = 0 ; i < arr . length ; i ++ ) { adj [ arr [ i ] [ 0 ] ] . push ( arr [ i ] [ 1 ] ) ; adj [ arr [ i ] [ 1 ] ] . push ( arr [ i ] [ 0 ] ) ; } visited = new Array ( N ) ; visited . fill ( false ) ; let v = [ ] ; num = 0 ; for ( let i = 0 ; i < N ; i ++ ) { if ( ! visited [ i ] ) { dfs ( i ) ; v . push ( num ) ; num = 0 ; } } let ans = N * ( N - 1 ) / 2 ; for ( let i = 0 ; i < v . length ; i ++ ) { ans -= ( v [ i ] * ( v [ i ] - 1 ) / 2 ) ; } document . write ( ans ) ; } let N = 6 ; let arr = [ [ 0 , 1 ] , [ 0 , 2 ] , [ 2 , 5 ] ] ; numberOfPairs ( N , arr ) ;