Number of pairs such that path between pairs has the two vertices A and B | Python 3 program to find the number of pairs such that the path between every pair contains two given vertices ; Function to perform DFS on the given graph by fixing the a vertex ; To mark a particular vertex as visited ; Variable to store the count of the vertices which can be reached from a ; Performing the DFS by iterating over the visited array ; If the vertex is not visited and removing the vertex b ; Function to return the number of pairs such that path between any two pairs consists of the given two vertices A and B ; Initializing the visited array and assigning it with 0 's ; Initially , the count of vertices is 0 ; Performing DFS by removing the vertex B ; Count the vertices which cannot be reached after removing the vertex B ; Again reinitializing the visited array ; Setting the count of vertices to 0 to perform the DFS again ; Performing the DFS by removing the vertex A ; Count the vertices which cannot be reached after removing the vertex A ; Multiplying both the vertices set ; Driver code ; Loop to store the graph
N = 1000001 NEW_LINE c = 0 NEW_LINE n = 0 NEW_LINE m = 0 NEW_LINE a = 0 NEW_LINE b = 0 NEW_LINE def dfs ( a , b , v , vis ) : NEW_LINE INDENT global c NEW_LINE vis [ a ] = 1 NEW_LINE c += 1 NEW_LINE for i in v [ a ] : NEW_LINE INDENT if ( vis [ i ] == 0 and i != b ) : NEW_LINE INDENT dfs ( i , b , v , vis ) NEW_LINE DEDENT DEDENT DEDENT def Calculate ( v ) : NEW_LINE INDENT global c NEW_LINE vis = [ 0 for i in range ( n + 1 ) ] NEW_LINE c = 0 NEW_LINE dfs ( a , b , v , vis ) NEW_LINE ans1 = n - c - 1 NEW_LINE vis = [ 0 for i in range ( len ( vis ) ) ] NEW_LINE c = 0 NEW_LINE dfs ( b , a , v , vis ) NEW_LINE ans2 = n - c - 1 NEW_LINE print ( ans1 * ans2 ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 7 NEW_LINE m = 7 NEW_LINE a = 3 NEW_LINE b = 5 NEW_LINE edges = [ [ 1 , 2 ] , [ 2 , 3 ] , [ 3 , 4 ] , [ 4 , 5 ] , [ 5 , 6 ] , [ 6 , 7 ] , [ 7 , 5 ] ] NEW_LINE v = [ [ ] for i in range ( n + 1 ) ] NEW_LINE for i in range ( m ) : NEW_LINE INDENT v [ edges [ i ] [ 0 ] ] . append ( edges [ i ] [ 1 ] ) NEW_LINE v [ edges [ i ] [ 1 ] ] . append ( edges [ i ] [ 0 ] ) NEW_LINE DEDENT Calculate ( v ) NEW_LINE DEDENT