Finding Astronauts from different countries | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void dfs ( int v , vector < vector < int > > & adj , vector < bool > & visited , int & num ) { visited [ v ] = true ; num ++ ; for ( int i = 0 ; i < adj [ v ] . size ( ) ; i ++ ) { if ( ! visited [ adj [ v ] [ i ] ] ) { dfs ( adj [ v ] [ i ] , adj , visited , num ) ; } } } void numberOfPairs ( int N , vector < vector < int > > arr ) { vector < vector < int > > adj ( N ) ; for ( vector < int > & i : arr ) { adj [ i [ 0 ] ] . push_back ( i [ 1 ] ) ; adj [ i [ 1 ] ] . push_back ( i [ 0 ] ) ; } vector < bool > visited ( N ) ; vector < int > v ; int num = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( ! visited [ i ] ) { dfs ( i , adj , visited , num ) ; v . push_back ( num ) ; num = 0 ; } } int ans = N * ( N - 1 ) / 2 ; for ( int i : v ) { ans -= ( i * ( i - 1 ) / 2 ) ; } cout << ans ; } int main ( ) { int N = 6 ; vector < vector < int > > arr = { { 0 , 1 } , { 0 , 2 } , { 2 , 5 } } ; numberOfPairs ( N , arr ) ; return 0 ; }