Number of pair of positions in matrix which are not accessible | Java 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 . ; Driver Code
import java . util . * ; class GFG { static int k ; static void dfs ( Vector < Integer > graph [ ] , boolean visited [ ] , int x ) { for ( int i = 0 ; i < graph [ x ] . size ( ) ; i ++ ) { if ( ! visited [ graph [ x ] . get ( i ) ] ) { ( k ) ++ ; visited [ graph [ x ] . get ( i ) ] = true ; dfs ( graph , visited , graph [ x ] . get ( i ) ) ; } } } static int countNonAccessible ( Vector < Integer > graph [ ] , int N ) { boolean [ ] visited = new boolean [ N * N + N ] ; int ans = 0 ; for ( int i = 1 ; i <= N * N ; i ++ ) { if ( ! visited [ i ] ) { visited [ i ] = true ; int k = 1 ; dfs ( graph , visited , i ) ; ans += k * ( N * N - k ) ; } } return ans ; } static void insertpath ( Vector < Integer > 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 ] . add ( b ) ; graph [ b ] . add ( a ) ; } public static void main ( String args [ ] ) { int N = 2 ; Vector [ ] graph = new Vector [ N * N + 1 ] ; for ( int i = 1 ; i <= N * N ; i ++ ) graph [ i ] = new Vector < Integer > ( ) ; insertpath ( graph , N , 1 , 1 , 1 , 2 ) ; insertpath ( graph , N , 1 , 2 , 2 , 2 ) ; System . out . println ( countNonAccessible ( graph , N ) ) ; } }