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
def dfs ( graph , visited , x , k ) : NEW_LINE INDENT for i in range ( len ( graph [ x ] ) ) : NEW_LINE INDENT if ( not visited [ graph [ x ] [ i ] ] ) : NEW_LINE INDENT k [ 0 ] += 1 NEW_LINE visited [ graph [ x ] [ i ] ] = True NEW_LINE dfs ( graph , visited , graph [ x ] [ i ] , k ) NEW_LINE DEDENT DEDENT DEDENT def countNonAccessible ( graph , N ) : NEW_LINE INDENT visited = [ False ] * ( N * N + N ) NEW_LINE ans = 0 NEW_LINE for i in range ( 1 , N * N + 1 ) : NEW_LINE INDENT if ( not visited [ i ] ) : NEW_LINE INDENT visited [ i ] = True NEW_LINE k = [ 1 ] NEW_LINE dfs ( graph , visited , i , k ) NEW_LINE ans += k [ 0 ] * ( N * N - k [ 0 ] ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def insertpath ( graph , N , x1 , y1 , x2 , y2 ) : NEW_LINE INDENT a = ( x1 - 1 ) * N + y1 NEW_LINE b = ( x2 - 1 ) * N + y2 NEW_LINE graph [ a ] . append ( b ) NEW_LINE graph [ b ] . append ( a ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 2 NEW_LINE graph = [ [ ] for i in range ( N * N + 1 ) ] NEW_LINE insertpath ( graph , N , 1 , 1 , 1 , 2 ) NEW_LINE insertpath ( graph , N , 1 , 2 , 2 , 2 ) NEW_LINE print ( countNonAccessible ( graph , N ) ) NEW_LINE DEDENT