Number of pair of positions in matrix which are not accessible | C ++ program to count number of pair of positions in matrix which are not accessible ; Counts number of vertices connected in a component containing x . Stores the count in k . ; Incrementing the number of node in a connected component . ; Return the number of count of non - accessible cells . ; Initialize count of connected vertices found by DFS starting from i . ; Update result ; Inserting the edge between edge . ; Mapping the cell coordinate into node number . ; Inserting the edge . ; Driven Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; void dfs ( vector < int > graph [ ] , bool visited [ ] , int x , int * k ) { for ( int i = 0 ; i < graph [ x ] . size ( ) ; i ++ ) { if ( ! visited [ graph [ x ] [ i ] ] ) { ( * k ) ++ ; visited [ graph [ x ] [ i ] ] = true ; dfs ( graph , visited , graph [ x ] [ i ] , k ) ; } } } int countNonAccessible ( vector < int > graph [ ] , int N ) { bool visited [ N * N + N ] ; memset ( visited , false , sizeof ( visited ) ) ; int ans = 0 ; for ( int i = 1 ; i <= N * N ; i ++ ) { if ( ! visited [ i ] ) { visited [ i ] = true ; int k = 1 ; dfs ( graph , visited , i , & k ) ; ans += k * ( N * N - k ) ; } } return ans ; } void insertpath ( vector < int > graph [ ] , int N , int x1 , int y1 , int x2 , int y2 ) { int a = ( x1 - 1 ) * N + y1 ; int b = ( x2 - 1 ) * N + y2 ; graph [ a ] . push_back ( b ) ; graph [ b ] . push_back ( a ) ; } int main ( ) { int N = 2 ; vector < int > graph [ N * N + 1 ] ; insertpath ( graph , N , 1 , 1 , 1 , 2 ) ; insertpath ( graph , N , 1 , 2 , 2 , 2 ) ; cout << countNonAccessible ( graph , N ) << endl ; return 0 ; }