Number of pairs such that path between pairs has the two vertices A and B | C # 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
using System ; using System . Collections . Generic ; class GFG { static int N = 1000001 ; static int c , n , m , a , b ; static void dfs ( int a , int b , List < int > [ ] v , int [ ] vis ) { vis [ a ] = 1 ; c ++ ; foreach ( int i in v [ a ] ) { if ( vis [ i ] == 0 && i != b ) dfs ( i , b , v , vis ) ; } } static void Calculate ( List < int > [ ] v ) { int [ ] vis = new int [ n + 1 ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) vis [ i ] = 0 ; c = 0 ; dfs ( a , b , v , vis ) ; int ans1 = n - c - 1 ; for ( int i = 0 ; i < n + 1 ; i ++ ) vis [ i ] = 0 ; c = 0 ; dfs ( b , a , v , vis ) ; int ans2 = n - c - 1 ; Console . Write ( ans1 * ans2 + " STRNEWLINE " ) ; } public static void Main ( String [ ] args ) { n = 7 ; m = 7 ; a = 3 ; b = 5 ; int [ , ] edges = { { 1 , 2 } , { 2 , 3 } , { 3 , 4 } , { 4 , 5 } , { 5 , 6 } , { 6 , 7 } , { 7 , 5 } } ; List < int > [ ] v = new List < int > [ n + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) { v [ i ] = new List < int > ( ) ; } for ( int i = 0 ; i < m ; i ++ ) { v [ edges [ i , 0 ] ] . Add ( edges [ i , 1 ] ) ; v [ edges [ i , 1 ] ] . Add ( edges [ i , 0 ] ) ; } Calculate ( v ) ; } }