ML 55

#include <iostream>

struct my_pair
{
    int a;
    int b;
};

struct vertex
{
    bool isterminal;
    int adj_list[26];
    bool is_exist[26];
};

struct cartesian_vertex
{
    int u;
    int v;
    bool isterminal;
    bool isvisited;
    struct my_pair adj_list[26];
    bool is_exist[26];
};

void addEdge(int i, int j, char symbol, struct vertex* DFA)
{
    int symbol_idx = static_cast<int>(symbol) - 97;
    DFA[i].adj_list[symbol_idx] = j;
    DFA[i].is_exist[symbol_idx] = true;
}

void Fill_DFA(int n, int k, int l, struct vertex* DFA)
{
    int u, v;
    char c;
    int terminals[k];

    for (int i = 0; i < k; ++i)
        std::cin >> terminals[i];

    for (int i = 0; i < k; ++i)
        DFA[terminals[i]].isterminal = true;

    for (int i = 0; i < n * l; ++i)
    {
        std::cin >> u >> c >> v;
        addEdge(u, v, c, DFA);
    }

    return;
}

void clean_DFA(struct vertex* DFA, int n)
{
    for (int i = 0; i < n; ++i)
    {
        DFA[i].isterminal = false;
        for (int j = 0; j < 26; ++j)
        {
            DFA[i].adj_list[j] = -1;
            DFA[i].is_exist[j] = false;
        }
    }
}

void clean_DFA_two(struct cartesian_vertex* DFA, int n)
{
    for (int i = 0; i < n; ++i)
    {
        DFA[i].isterminal = false;
        DFA[i].isvisited = false;
        for (int j = 0; j < 26; ++j)
            DFA[i].is_exist[j] = false;
    }
}

void cartesian_product(struct cartesian_vertex* dec_graph, struct vertex* DFA_one,
    struct vertex* DFA_two, int n_one, int n_two)
{

    int N = n_one * n_two;
    cartesian_vertex buff;
    struct my_pair dec_ver;

    clean_DFA_two(dec_graph, N);

    for (int i = 0; i < n_one; ++i)
    {
        for (int j = 0; j < n_two; ++j)
        {
            int idx = i * n_two + j;

            dec_graph[idx].u = i;
            dec_graph[idx].v = j;
            dec_graph[idx].isterminal = (DFA_one[i].isterminal != DFA_two[j].isterminal);

            for (int k = 0; k < 26; ++k)
            {
                if (DFA_one[i].is_exist[k] && DFA_two[j].is_exist[k])
                {
                    dec_ver.a = DFA_one[i].adj_list[k];
                    dec_ver.b = DFA_two[j].adj_list[k];
                    dec_graph[idx].adj_list[k] = dec_ver;
                    dec_graph[idx].is_exist[k] = true;
                }
            }
        }
    }
}

void DFS(int v_idx, struct cartesian_vertex* graph, bool& is_equiv, int n_two)
{

    int a, b;
    if (is_equiv)
    {
        if (graph[v_idx].isterminal)
        {
            is_equiv = false;
            return;
        }

        graph[v_idx].isvisited = true;
        for (int i = 0; i < 26; ++i)
        {
            if (graph[v_idx].is_exist[i])
            {
                a = graph[v_idx].adj_list[i].a;
                b = graph[v_idx].adj_list[i].b;
                int idx = a * n_two + b;
                if (not graph[idx].isvisited)
                    DFS(idx, graph, is_equiv, n_two);
            }
        }
    }
    return;
}

int main()
{

    int n_one, k_one, l_one;
    int n_two, k_two, l_two;

    std::cin >> n_one >> k_one >> l_one;
    vertex DFA_one[n_one];
    clean_DFA(DFA_one, n_one);
    Fill_DFA(n_one, k_one, l_one, DFA_one);

    std::cin >> n_two >> k_two >> l_two;
    vertex DFA_two[n_two];
    clean_DFA(DFA_two, n_two);
    Fill_DFA(n_two, k_two, l_two, DFA_two);

    int N = n_one * n_two;
    struct cartesian_vertex dec_graph[N];
    cartesian_product(dec_graph, DFA_one, DFA_two, n_one, n_two);

    bool is_equiv = true;
    DFS(0, dec_graph, is_equiv, n_two);

    if (is_equiv)
        std::cout << "EQUIVALENT";
    else
        std::cout << "NOT EQUIVALENT";

    return 0;
}