Encuentre todos los bordes compatibles y no compatibles de una máquina

Dada una máquina en el lenguaje formal de N estados y M pares de combinaciones de salida en forma de array 2D arr[][] . Cada fila (digamos r ) de arr[][] indica los Nodes de ‘A’ a ‘Z’ y cada par de una columna (digamos (a, b) ) indica el cambio de estado del Node r al Node a través del estado segundo _ La tarea es encontrar los bordes compatibles y no compatibles del lenguaje formal.
Nota: se dice que Edge (A, B) es compatible ya que todos los siguientes estados y salidas son iguales o no están especificados en A, B correspondientes a cada columna.
Ejemplo:

Entrada: N = 6, M = 4, 
arr[][] = { { ‘-‘, ‘-‘, ‘C’, ‘1’, ‘E’, ‘1’, ‘B’, ‘1’ } , 
{ ‘E’, ‘0’, ‘-‘, ‘-‘, ‘-‘, ‘-‘, ‘-‘, ‘-‘ }, 
{ ‘F’, ‘0’, ‘F’, ‘1 ‘, ‘-‘, ‘-‘, ‘-‘, ‘-‘ }, 
{ ‘-‘, ‘-‘, ‘-‘, ‘-‘, ‘B’, ‘1’, ‘-‘, ‘- ‘ }, 
{ ‘-‘, ‘-‘, ‘F’, ‘0’, ‘A’, ‘0’, ‘D’, ‘1’ }, 
{ ‘C’, ‘0’, ‘-‘, ‘-‘, ‘B’, ‘0’, ‘C’, ‘1’ } } 
Salida: 
Bordes no compatibles 
(A, E) (A, F) (B, F) (C, E) (D, E ) (D, F) 
Bordes compatibles 
(A, B)(A, C)(A, D)(B, C)(B, D)(B, E)(C, D)(C, F)(E) , F)
Entrada: N = 4, M = 4, 
arr[][] = { { ‘-‘, ‘-‘, ‘C’, ‘1’, ‘E’, ‘1’, ‘B’, ‘ 1’ }, 
{ ‘-‘, ‘-‘, ‘-‘, ‘-‘, ‘B’, ‘1’, ‘-‘, ‘-‘ }, 
{ ‘-‘, ‘-‘, ‘F’ , ‘0’, ‘A’, ‘0’, ‘D’, ‘1’ }, 
{ ‘C’, ‘0’, ‘-‘, ‘-‘, ‘B’, ‘0’, ‘C’, ‘1’ } } 
Salida: 
bordes no compatibles 
(A, C) (A, D) ( B, C) (B, D) 
Bordes compatibles 
(A, B)(C, D)

Acercarse:

1. Para todas las combinaciones posibles (digamos (a,b) ) de los Nodes, verifique si hay algún camino posible presente en el lenguaje formal a través de cualquier número de estados como: 
   • Si el estado a través del Node a está vacío , busque el siguiente par de Nodes.
   • Si el estado atravesado actual (por ejemplo, el Node b ) a través del Node a no está vacío y si el estado de salida a través del Node a al Node b no es el mismo, entonces verifique recursivamente la ruta del Node a al Node b .
   • Si el estado de salida es el mismo, entonces tiene un borde directo entre el Node a y el Node b .
2. Si la ruta se encuentra entre cualquier par de Nodes, entonces el par de Nodes es parte de un Node compatible.
3. Almacene el par anterior de Nodes compatibles en una array Mat[][] .
4. Recorra el Mat[][] para todos los pares posibles, y si ese par está presente en Mat[][], entonces imprímalo como Nodes compatibles De lo contrario, es un Node No compatible.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
const int M = 8;
 
// Function to find the compatible and
// non-compatible for a given formal language
void findEdges(char arr[][M], int n, int m)
{
 
    // To store the compatible edges
    char mat[1000][1000] = { 'x' };
 
    // Loop over every pair of nodes in the
    // given formal language
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
 
            // Traverse through the output
            // column and compare it between
            // each set of pairs of nodes
            for (int k = 0; k < 2 * m; k += 2) {
 
                // If the output is not
                // specified then leave the
                // edge unprocessed
                if (arr[i][k + 1] == '-'
                    || arr[j][k + 1] == '-') {
                    continue;
                }
 
                // If the output of states
                // doesn't match then not
                // compatible.
                if (arr[i][k + 1] != arr[j][k + 1]) {
 
                    // Mark the not compatible
                    // edges in the matrix with
                    // character 'v'
                    mat[i][j] = 'v';
                    mat[j][i] = 'v';
                    break;
                }
            }
        }
    }
 
    int nn = n;
 
    // Loop over all node to find other non
    // compatible edges
    while (nn--) {
 
        // Loop over every pair of nodes in
        // the given formal language
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
 
                int k;
                for (k = 0; k < m; k += 2) {
 
                    // If the output is
                    // not specified then
                    // leave edge unprocessed
                    if (arr[i][k + 1] == '-'
                        || arr[j][k + 1] == '-') {
                        continue;
                    }
 
                    // If output is not equal
                    // then break as non-compatible
                    if (arr[i][k + 1] != arr[j][k + 1]) {
                        break;
                    }
                }
 
                if (k < m) {
                    continue;
                }
 
                for (k = 0; k < m; k += 2) {
 
                    // If next states are unspecified
                    // then continue
                    if (arr[i][k] == '-'
                        || arr[j][k] == '-') {
                        continue;
                    }
 
                    // If the states are not equal
                    if (arr[i][k] != arr[j][k]) {
                        int x = arr[i][k] - 'A';
                        int y = arr[j][k] - 'A';
 
                        // If the dependent edge
                        // is not compatible then
                        // this edge is also not
                        // compatible
                        if (mat[x][y] == 'v') {
                            mat[i][j] = 'v';
                            mat[j][i] = 'v';
                            break;
                        }
                    }
                }
            }
        }
    }
 
    // Output all Non-compatible Edges
    printf("Not Compatible Edges \n");
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (mat[i][j] == 'v') {
                printf("(%c, %c) ", i + 65, j + 65);
            }
        }
    }
    printf("\n");
 
    // Output all Compatible Edges
    printf("Compatible Edges \n");
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (mat[i][j] != 'v') {
                printf("(%c, %c)", i + 65, j + 65);
            }
        }
    }
}
 
// Driver Code
int main()
{
    int n = 6, m = 4;
 
    char arr[][8] = { { '-', '-', 'C', '1', 'E', '1', 'B', '1' },
                      { 'E', '0', '-', '-', '-', '-', '-', '-' },
                      { 'F', '0', 'F', '1', '-', '-', '-', '-' },
                      { '-', '-', '-', '-', 'B', '1', '-', '-' },
                      { '-', '-', 'F', '0', 'A', '0', 'D', '1' },
                      { 'C', '0', '-', '-', 'B', '0', 'C', '1' } };
 
    findEdges(arr, n, m);
    return 0;
}

// Java implementation of the above approach
import java.util.*;
  
class GFG{
     
static int M = 8;
  
// Function to find the compatible and
// non-compatible for a given formal language
static void findEdges(char arr[][], int n, int m)
{
  
    // To store the compatible edges
    char [][]mat = new char[1000][1000];
  
    // Loop over every pair of nodes in the
    // given formal language
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
  
            // Traverse through the output
            // column and compare it between
            // each set of pairs of nodes
            for(int k = 0; k < 2 * m; k += 2)
            {
  
                // If the output is not
                // specified then leave the
                // edge unprocessed
                if (arr[i][k + 1] == '-' ||
                    arr[j][k + 1] == '-')
                {
                    continue;
                }
  
                // If the output of states
                // doesn't match then not
                // compatable.
                if (arr[i][k + 1] != arr[j][k + 1])
                {
  
                    // Mark the not compatable
                    // edges in the matrix with
                    // character 'v'
                    mat[i][j] = 'v';
                    mat[j][i] = 'v';
                    break;
                }
            }
        }
    }
  
    int nn = n;
  
    // Loop over all node to find other non
    // compatable edges
    while (nn-- > 0)
    {
  
        // Loop over every pair of nodes in
        // the given formal language
        for(int i = 0; i < n; i++)
        {
            for(int j = i + 1; j < n; j++)
            {
                int k;
                for(k = 0; k < m; k += 2)
                {
  
                    // If the output is
                    // not specified then
                    // leave edge unprocessed
                    if (arr[i][k + 1] == '-' ||
                        arr[j][k + 1] == '-')
                    {
                        continue;
                    }
  
                    // If output is not equal
                    // then break as non-compatable
                    if (arr[i][k + 1] !=
                        arr[j][k + 1])
                    {
                        break;
                    }
                }
  
                if (k < m)
                {
                    continue;
                }
  
                for(k = 0; k < m; k += 2)
                {
  
                    // If next states are unspecified
                    // then continue
                    if (arr[i][k] == '-' ||
                        arr[j][k] == '-')
                    {
                        continue;
                    }
  
                    // If the states are not equal
                    if (arr[i][k] != arr[j][k])
                    {
                        int x = arr[i][k] - 'A';
                        int y = arr[j][k] - 'A';
  
                        // If the dependent edge
                        // is not compatable then
                        // this edge is also not
                        // compatable
                        if (mat[x][y] == 'v')
                        {
                            mat[i][j] = 'v';
                            mat[j][i] = 'v';
                            break;
                        }
                    }
                }
            }
        }
    }
  
    // Output all Non-compatable Edges
    System.out.printf("Not Compatable Edges \n");
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if (mat[i][j] == 'v')
            {
                System.out.printf("(%c, %c) ",
                                  i + 65, j + 65);
            }
        }
    }
    System.out.printf("\n");
  
    // Output all Compatable Edges
    System.out.printf("Compatable Edges \n");
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if (mat[i][j] != 'v')
            {
                System.out.printf("(%c, %c)",
                                  i + 65, j + 65);
            }
        }
    }
}
  
// Driver Code
public static void main(String[] args)
{
    int n = 6, m = 4;
  
    char arr[][] = { { '-', '-', 'C', '1',
                       'E', '1', 'B', '1' },
                     { 'E', '0', '-', '-',
                       '-', '-', '-', '-' },
                     { 'F', '0', 'F', '1',
                       '-', '-', '-', '-' },
                     { '-', '-', '-', '-',
                       'B', '1', '-', '-' },
                     { '-', '-', 'F', '0',
                       'A', '0', 'D', '1' },
                     { 'C', '0', '-', '-',
                       'B', '0', 'C', '1' } };
  
    findEdges(arr, n, m);
}
}
  
// This code is contributed by Amit Katiyar

// C# implementation of
// the above approach
using System;
class GFG{
     
static int M = 8;
  
// Function to find the
//compatible and non-compatible
// for a given formal language 
static void findEdges(char [,]arr,
                      int n, int m)
{
  // To store the compatible edges
  char [,]mat = new char[1000, 1000];
 
  // Loop over every pair of
  // nodes in the given
  // formal language
  for(int i = 0; i < n; i++)
  {
    for(int j = i + 1; j < n; j++)
    {
      // Traverse through the output
      // column and compare it between
      // each set of pairs of nodes
      for(int k = 0; k < 2 * m; k += 2)
      {
        // If the output is not
        // specified then leave the
        // edge unprocessed
        if (arr[i, k + 1] == '-' ||
            arr[j, k + 1] == '-')
        {
          continue;
        }
 
        // If the output of states
        // doesn't match then not
        // compatable.
        if (arr[i, k + 1] != arr[j, k + 1])
        {
          // Mark the not compatable
          // edges in the matrix with
          // character 'v'
          mat[i, j] = 'v';
          mat[j, i] = 'v';
          break;
        }
      }
    }
  }
 
  int nn = n;
 
  // Loop over all node to find other non
  // compatable edges
  while (nn-- > 0)
  {
 
    // Loop over every pair of nodes in
    // the given formal language
    for(int i = 0; i < n; i++)
    {
      for(int j = i + 1; j < n; j++)
      {
        int k;
        for(k = 0; k < m; k += 2)
        {
          // If the output is
          // not specified then
          // leave edge unprocessed
          if (arr[i, k + 1] == '-' ||
              arr[j, k + 1] == '-')
          {
            continue;
          }
 
          // If output is not equal
          // then break as non-compatable
          if (arr[i, k + 1] !=
              arr[j, k + 1])
          {
            break;
          }
        }
 
        if (k < m)
        {
          continue;
        }
 
        for(k = 0; k < m; k += 2)
        {
          // If next states are unspecified
          // then continue
          if (arr[i, k] == '-' ||
              arr[j, k] == '-')
          {
            continue;
          }
 
          // If the states are not equal
          if (arr[i, k] != arr[j, k])
          {
            int x = arr[i, k] - 'A';
            int y = arr[j, k] - 'A';
 
            // If the dependent edge
            // is not compatable then
            // this edge is also not
            // compatable
            if (mat[x, y] == 'v')
            {
              mat[i, j] = 'v';
              mat[j, i] = 'v';
              break;
            }
          }
        }
      }
    }
  }
 
  // Output all Non-compatable Edges
  Console.Write("Not Compatable Edges \n");
  for(int i = 0; i < n; i++)
  {
    for(int j = i + 1; j < n; j++)
    {
      if (mat[i, j] == 'v')
      {
        Console.Write("({0}, {1}) ",
                      (char)(i + 65),
                      (char)(j + 65));
      }
    }
  }
  Console.Write("\n");
 
  // Output all Compatable Edges
  Console.Write("Compatable Edges \n");
  for(int i = 0; i < n; i++)
  {
    for(int j = i + 1; j < n; j++)
    {
      if (mat[i, j] != 'v')
      {
        Console.Write("({0}, {1})",
                      (char)(i + 65),
                      (char)(j + 65));
      }
    }
  }
}
  
// Driver Code
public static void Main(String[] args)
{
  int n = 6, m = 4;
  char [,]arr = {{'-', '-', 'C', '1',
                  'E', '1', 'B', '1'},
                 {'E', '0', '-', '-',
                  '-', '-', '-', '-'},
                 {'F', '0', 'F', '1',
                  '-', '-', '-', '-'},
                 {'-', '-', '-', '-',
                  'B', '1', '-', '-'},
                 {'-', '-', 'F', '0',
                  'A', '0', 'D', '1'},
                 {'C', '0', '-', '-',
                  'B', '0', 'C', '1'}};
  findEdges(arr, n, m);
}
}
  
// This code is contributed by 29AjayKumar

metro

Complejidad de tiempo: O(M*N ³ ), donde N es el número de estados y M es la salida para cada estado.