Finding Astronauts from different countries | C # 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
using System ; using System . Collections . Generic ; class GFG { static List < List < int > > adj ; static bool [ ] visited ; static int num ; static void dfs ( int v ) { visited [ v ] = true ; num ++ ; for ( int i = 0 ; i < adj [ v ] . Count ; i ++ ) { if ( ! visited [ adj [ v ] [ i ] ] ) { dfs ( adj [ v ] [ i ] ) ; } } } static void numberOfPairs ( int N , int [ , ] arr ) { adj = new List < List < int > > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { adj . Add ( new List < int > ( ) ) ; } for ( int i = 0 ; i < 2 ; i ++ ) { adj [ arr [ i , 0 ] ] . Add ( arr [ i , 1 ] ) ; adj [ arr [ i , 1 ] ] . Add ( arr [ i , 0 ] ) ; } visited = new bool [ N ] ; Array . Fill ( visited , false ) ; List < int > v = new List < int > ( ) ; 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 . Count ; i ++ ) { ans -= ( v [ i ] * ( v [ i ] - 1 ) / 2 ) + 1 ; } Console . Write ( ans ) ; } static void Main ( ) { int N = 6 ; int [ , ] arr = { { 0 , 1 } , { 0 , 2 } , { 2 , 5 } } ; numberOfPairs ( N , arr ) ; } }