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 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 1000001 ; int c , n , m , a , b ; void dfs ( int a , int b , vector < int > v [ ] , int vis [ ] ) { vis [ a ] = 1 ; c ++ ; for ( auto i : v [ a ] ) { if ( ! vis [ i ] && i != b ) dfs ( i , b , v , vis ) ; } } void Calculate ( vector < int > v [ ] ) { int vis [ n + 1 ] ; memset ( vis , 0 , sizeof ( vis ) ) ; c = 0 ; dfs ( a , b , v , vis ) ; int ans1 = n - c - 1 ; memset ( vis , 0 , sizeof ( vis ) ) ; c = 0 ; dfs ( b , a , v , vis ) ; int ans2 = n - c - 1 ; cout << ans1 * ans2 << " STRNEWLINE " ; } int main ( ) { n = 7 , m = 7 , a = 3 , b = 5 ; int edges [ ] [ 2 ] = { { 1 , 2 } , { 2 , 3 } , { 3 , 4 } , { 4 , 5 } , { 5 , 6 } , { 6 , 7 } , { 7 , 5 } } ; vector < int > v [ n + 1 ] ; for ( int i = 0 ; i < m ; i ++ ) { v [ edges [ i ] [ 0 ] ] . push_back ( edges [ i ] [ 1 ] ) ; v [ edges [ i ] [ 1 ] ] . push_back ( edges [ i ] [ 0 ] ) ; } Calculate ( v ) ; return 0 ; }