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
adj = [ ] NEW_LINE visited = [ ] NEW_LINE num = 0 NEW_LINE def dfs ( v ) : NEW_LINE INDENT global adj , visited , num NEW_LINE visited [ v ] = True NEW_LINE num += 1 NEW_LINE for i in range ( len ( adj [ v ] ) ) : NEW_LINE INDENT if ( not visited [ adj [ v ] [ i ] ] ) : NEW_LINE INDENT dfs ( adj [ v ] [ i ] ) NEW_LINE DEDENT DEDENT DEDENT def numberOfPairs ( N , arr ) : NEW_LINE INDENT global adj , visited , num NEW_LINE adj = [ ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT adj . append ( [ ] ) NEW_LINE DEDENT for i in range ( len ( arr ) ) : NEW_LINE INDENT adj [ arr [ i ] [ 0 ] ] . append ( arr [ i ] [ 1 ] ) NEW_LINE adj [ arr [ i ] [ 1 ] ] . append ( arr [ i ] [ 0 ] ) NEW_LINE DEDENT visited = [ False ] * ( N ) NEW_LINE v = [ ] NEW_LINE num = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( not visited [ i ] ) : NEW_LINE INDENT dfs ( i ) NEW_LINE v . append ( num ) NEW_LINE num = 0 NEW_LINE DEDENT DEDENT ans = N * int ( ( N - 1 ) / 2 ) NEW_LINE for i in range ( len ( v ) ) : NEW_LINE INDENT ans -= ( v [ i ] * int ( ( v [ i ] - 1 ) / 2 ) ) NEW_LINE DEDENT ans += 1 NEW_LINE print ( ans ) NEW_LINE DEDENT N = 6 NEW_LINE arr = [ [ 0 , 1 ] , [ 0 , 2 ] , [ 2 , 5 ] ] NEW_LINE numberOfPairs ( N , arr ) NEW_LINE