Número de pares de posiciones en la array que no son accesibles

Dado un entero positivo N . Considere una array de NXN . No se puede acceder a ninguna celda desde ninguna otra celda, excepto el par de celdas dado en forma de (x1, y1), (x2, y2), es decir, hay un camino (accesible) entre (x2, y2) y (x1, y1) . La tarea es encontrar el conteo de pares (a1, b1), (a2, b2) tal que la celda (a2, b2) no sea accesible desde (a1, b1).

Ejemplos: 

Input : N = 2
Allowed path 1: (1, 1) (1, 2)
Allowed path 2: (1, 2) (2, 2)
Output : 6
Cell (2, 1) is not accessible from any cell
and no cell is accessible from it.

(1, 1) - (2, 1)
(1, 2) - (2, 1)
(2, 2) - (2, 1)
(2, 1) - (1, 1)
(2, 1) - (1, 2)
(2, 1) - (2, 2)

Considere cada celda como un Node, numerado del 1 al N*N. Cada celda (x, y) se puede asignar a un número usando (x – 1)*N + y. Ahora, considere cada ruta permitida dada como un borde entre Nodes. Esto formará un conjunto disjunto del componente conectado. Ahora, utilizando Depth First Traversal o Breadth First Traversal , podemos encontrar fácilmente el número de Nodes o el tamaño de un componente conectado, digamos x. Ahora, el número de rutas no accesibles es x*(N*N – x). De esta manera podemos encontrar caminos no accesibles para cada camino conectado.

A continuación se muestra la implementación de este enfoque: 

// C++ program to count number of pair of positions
// in matrix which are not accessible
#include<bits/stdc++.h>
using namespace std;
 
// 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);
}
 
// Driven Program
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;
}

// Java program to count number of
// pair of positions in matrix
// which are not accessible
import java.util.*;
@SuppressWarnings("unchecked")
class GFG {
 
    static int k;
 
    // Counts number of vertices connected
    // in a component containing x.
    // Stores the count in 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)]) {
                // Incrementing the number of node in
                // a connected component.
                (k)++;
 
                visited[graph[x].get(i)] = true;
                dfs(graph, visited, graph[x].get(i));
            }
        }
    }
 
    // Return the number of count of non-accessible cells.
    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++) {
             
              k = 0;
            if (!visited[i]) {
                visited[i] = true;
 
                // Initialize count of connected
                // vertices found by DFS starting
                // from i.
                k++;
                dfs(graph, visited, i);
 
                // Update result
                ans += k * (N * N - k);
            }
        }
        return ans;
    }
 
    // Inserting the edge between edge.
    static void insertpath(Vector<Integer> 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].add(b);
        graph[b].add(a);
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int N = 2;
 
        Vector<Integer>[] 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, 2, 1, 2, 2);
 
        System.out.println(countNonAccessible(graph, N));
    }
}
 
// This code is contributed by 29AjayKumar
// This code is corrected by Prithi_Dey

# Python3 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.
def dfs(graph,visited, x, k):
    for i in range(len(graph[x])):
        if (not visited[graph[x][i]]):
             
            # Incrementing the number of node 
            # in a connected component.
            k[0] += 1
 
            visited[graph[x][i]] = True
            dfs(graph, visited, graph[x][i], k)
 
# Return the number of count of
# non-accessible cells.
def countNonAccessible(graph, N):
    visited = [False] * (N * N + N)
 
    ans = 0
    for i in range(1, N * N + 1):
        if (not visited[i]):
            visited[i] = True
 
            # Initialize count of connected
            # vertices found by DFS starting
            # from i.
            k = [1]
            dfs(graph, visited, i, k)
 
            # Update result
            ans += k[0] * (N * N - k[0])
    return ans
 
# Inserting the edge between edge.
def insertpath(graph, N, x1, y1, x2, y2):
     
    # Mapping the cell coordinate
    # into node number.
    a = (x1 - 1) * N + y1
    b = (x2 - 1) * N + y2
 
    # Inserting the edge.
    graph[a].append(b)
    graph[b].append(a)
 
# Driver Code
if __name__ == '__main__':
 
    N = 2
 
    graph = [[] for i in range(N*N + 1)]
 
    insertpath(graph, N, 1, 1, 1, 2)
    insertpath(graph, N, 1, 2, 2, 2)
 
    print(countNonAccessible(graph, N))
 
# This code is contributed by PranchalK

// C# program to count number of
// pair of positions in matrix
// which are not accessible
using System;
using System.Collections.Generic;
 
class GFG
{
static int k;
 
// Counts number of vertices connected
// in a component containing x.
// Stores the count in k.
static void dfs(List<int> []graph,
                bool []visited, int x)
{
    for (int i = 0; i < graph[x].Count; 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]);
        }
    }
}
 
// Return the number of count
// of non-accessible cells.
static int countNonAccessible(List<int> []graph,
                                   int N)
{
    bool []visited = new bool[N * N + N];
 
    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);
 
            // Update result
            ans += k * (N * N - k);
        }
    }
    return ans;
}
 
// Inserting the edge between edge.
static void insertpath(List<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].Add(b);
    graph[b].Add(a);
}
 
// Driver Code
public static void Main(String []args)
{
    int N = 2;
 
    List<int>[] graph = new List<int>[N * N + 1];
    for (int i = 1; i <= N * N; i++)
        graph[i] = new List<int>();
    insertpath(graph, N, 1, 1, 1, 2);
    insertpath(graph, N, 1, 2, 2, 2);
 
    Console.WriteLine(countNonAccessible(graph, N));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// JavaScript program to count number of
// pair of positions in matrix
// which are not accessible
 
let k;
 
// Counts number of vertices connected
// in a component containing x.
// Stores the count in k.
function dfs(graph,visited,x)
{
    for (let i = 0; i < graph[x].length; 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]);
        }
    }
}
 
// Return the number of count of non-accessible cells.
function countNonAccessible(graph,N)
{
    let visited = new Array(N * N + N);
   
    let ans = 0;
    for (let i = 1; i <= N * N; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
   
            // Initialize count of connected
            // vertices found by DFS starting
            // from i.
            let k = 1;
            dfs(graph, visited, i);
   
            // Update result
            ans += k * (N * N - k);
        }
    }
    return ans;
}
 
// Inserting the edge between edge.
function insertpath(graph,N,x1,y1,x2,y2)
{
    // Mapping the cell coordinate into node number.
    let a = (x1 - 1) * N + y1;
    let b = (x2 - 1) * N + y2;
   
    // Inserting the edge.
    graph[a].push(b);
    graph[b].push(a);
}
 
// Driver Code
let N = 2;
   
let graph = new Array(N * N + 1);
for (let i = 1; i <= N * N; i++)
    graph[i] = [];
insertpath(graph, N, 1, 1, 1, 2);
insertpath(graph, N, 1, 2, 2, 2);
 
document.write(countNonAccessible(graph, N));
 
 
// This code is contributed by rag2127
 
</script>

6

Complejidad temporal: O(N * N).

Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.