Number of pair of positions in matrix which are not accessible - GeeksforGeeks

Number of pair of positions in matrix which are not accessible - GeeksforGeeks
Given a positive integer N. Consider a matrix of N X N. No cell can be accessible from any other cell, except the given pair cell in the form of (x1, y1), (x2, y2) i.e there is a path (accessible) between (x2, y2) to (x1, y1). The task is to find the count of pairs (a1, b1), (a2, b2) such that cell (a2, b2) is not accessible from (a1, b1).

Consider each cell as a node, numbered from 1 to N*N. Each cell (x, y) can be map to number using (x – 1)*N + y. Now, consider each given allowed path as an edge between nodes. This will form a disjoint set of the connected component. Now, using Depth First Traversal or Breadth First Traversal, we can easily find the number of nodes or size of a connected component, say x. Now, count of non-accessible paths are x*(N*N – x). This way we can find non-accessible paths for each connected path.

Time Complexity : O(N*N).

// Counts number of vertices connected in a component

// containing x. Stores the count in k.

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]])

        {

            // Incrementing the number of node in

            // a connected component.

            (*k)++;

 

            visited[graph[x][i]] = true;

            dfs(graph, visited, graph[x][i], k);

        }

    }

}

 

// Return the number of count of non-accessible cells.

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;

 

            // Initialize count of connected

            // vertices found by DFS starting

            // from i.

            int k = 1;

            dfs(graph, visited, i, &k);

 

            // Update result

            ans += k * (N*N - k);

        }

    }

    return ans;

}

 

// Inserting the edge between edge.

void insertpath(vector<int> graph[], int N, int x1,

                             int y1, int x2, int y2)

{

    // Mapping the cell coordinate into node number.

    int a = (x1 - 1) * N + y1;

    int b = (x2 - 1) * N + y2;

 

    // Inserting the edge.

    graph[a].push_back(b);

    graph[b].push_back(a);

}

Read full article from Number of pair of positions in matrix which are not accessible - GeeksforGeeks