Compruebe si la permutación dada es un DFS de gráfico válido

Dado un gráfico con N Nodes numerados del 1 al N y M aristas y una array de números del 1 al N. Compruebe si es posible obtener alguna permutación de la array aplicando DFS (Depth First Traversal) en el gráfico dado.
Requisitos previos: DFS | Mapa en CPP

Ejemplos:  

Input: N = 3, M = 2
        Edges are:
        1) 1-2
        2) 2-3
        P = {1, 2, 3}
Output: YES
Explanation: 
Since there are edges between 
1-2 and 2-3, therefore we can 
have DFS in the order 1-2-3

Input: N = 3, M = 2
        Edges are:
        1) 1-2
        2) 2-3
        P = {1, 3, 2}
Output: NO
Explanation: 
Since there is no edge between 1 and 3,
the DFS traversal is not possible 
in the order of given permutation.

Enfoque: Suponemos que el gráfico de entrada se representa como una lista de adyacencia . La idea es ordenar primero todas las listas de adyacencia según el orden de entrada, luego atravesar el gráfico dado comenzando desde el primer Node en la permutación dada. Si visitamos todos los vértices en el mismo orden, entonces la permutación dada es un DFS válido . 

1. Almacene los índices de cada número en la permutación dada en un mapa hash.
2. Ordene cada lista de adyacencia de acuerdo con los índices de permutación, ya que es necesario mantener el orden.
3. Realice la búsqueda transversal en profundidad con el Node de origen como primer número de la permutación dada.
4. Mantenga una variable de contador y en cada llamada recursiva, verifique si el contador ha alcanzado la cantidad de Nodes, es decir, N y establezca el indicador en 1. Si el indicador es 0 después de completar el DFS, la respuesta es ‘NO’; de lo contrario, ‘SÍ’

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

// C++ program to check if given
// permutation can be obtained
// upon DFS traversal on given graph
#include <bits/stdc++.h>
using namespace std;
 
// To track of DFS is valid or not.
bool flag = false;
 
// HashMap to store the indexes
// of given permutation
map<int, int> mp;
 
// Comparator function for sort
bool cmp(int a, int b)
{
    // Sort according ascending
    // order of indexes
    return mp[a] < mp[b];
}
 
// Graph class represents an undirected
// using adjacency list representation
class Graph {
    int V; // No. of vertices
    int counter; // Counter variable
 
public:
    // Pointer to an array containing
    // adjacency lists
    list<int>* adj;
 
    Graph(int V); // Constructor
 
    // function to add an edge to graph
    void addEdge(int u, int v);
 
    // DFS traversal of the vertices
    // reachable from v
    void DFS(int v, int Perm[]);
};
 
Graph::Graph(int V)
{
    this->V = V;
    this->counter = 0;
    adj = new list<int>[V + 1];
}
 
void Graph::addEdge(int u, int v)
{
 
    // Add v to u’s list.
    adj[u].push_back(v);
 
    // Add u to v's list
    adj[v].push_back(u);
}
 
// DFS traversal of the
// vertices reachable from v.
void Graph::DFS(int v, int Perm[])
{
    // Increment counter for
    // every node being traversed
    counter++;
 
    // Check if counter has
    // reached number of vertices
    if (counter == V) {
 
        // Set flag to 1
        flag = 1;
        return;
    }
 
    // Recur for all vertices adjacent
    // to this vertices only if it
    // lies in the given permutation
    list<int>::iterator i;
    for (i = adj[v].begin();
         i != adj[v].end(); i++) {
 
        // if the current node equals to
        // current element of permutation
        if (*i == Perm[counter])
            DFS(*i, Perm);
    }
}
 
// Returns true if P[] is a valid DFS of given
// graph. In other words P[] can be obtained by
// doing a DFS of the graph.
bool checkPermutation(
    int N, int M,
    vector<pair<int, int> > V,
    int P[])
{
 
    // Create the required graph with
    // N vertices and M edges
    Graph G(N);
 
    // Add Edges to Graph G
    for (int i = 0; i < M; i++)
        G.addEdge(V[i].first,
                  V[i].second);
 
    for (int i = 0; i < N; i++)
        mp[P[i]] = i;
 
    // Sort every adjacency
    // list according to HashMap
    for (int i = 1; i <= N; i++)
        G.adj[i].sort(cmp);
 
    // Call DFS with source node as P[0]
    G.DFS(P[0], P);
 
    // If Flag has been set to 1, means
    // given permutation is obtained
    // by DFS on given graph
    return flag;
}
 
// Driver code
int main()
{
    // Number of vertices
    // and number of edges
    int N = 3, M = 2;
 
    // Vector of pair to store edges
    vector<pair<int, int> > V;
 
    V.push_back(make_pair(1, 2));
    V.push_back(make_pair(2, 3));
 
    int P[] = { 1, 2, 3 };
 
    // Return the answer
    if (checkPermutation(N, M, V, P))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
 
    return 0;
}

// Java program to check if given
// permutation can be obtained
// upon DFS traversal on given graph
 
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
 
public class GFG {
    // To track of DFS is valid or not.
    static boolean flag = false;
 
    // HashMap to store the indexes
    // of given permutation
    static HashMap<Integer, Integer> mp
        = new HashMap<Integer, Integer>();
 
    // Graph class represents an undirected
    // using adjacency list representation
    static class Graph {
        int V; // No. of vertices
        int counter; // Counter variable
 
        // Pointer to an array containing
        // adjacency lists
        ArrayList<Integer> adj[];
 
        @SuppressWarnings("unchecked")
        Graph(int V)
        { // Constructor
            this.V = V;
 
            adj = new ArrayList[V + 1];
            for (int i = 0; i <= V; i++)
                adj[i] = new ArrayList<Integer>();
        }
 
        // function to add an edge to graph
        void addEdge(int u, int v)
        {
            // Add v to u’s list.
            adj[u].add(v);
 
            // Add u to v's list
            adj[v].add(u);
        }
 
        // DFS traversal of the vertices
        // reachable from v
        void DFS(int v, int Perm[])
        {
            // Increment counter for
            // every node being traversed
            counter++;
 
            // Check if counter has
            // reached number of vertices
            if (counter == V) {
 
                // Set flag to 1
                flag = true;
                return;
            }
 
            // Recur for all vertices adjacent
            // to this vertices only if it
            // lies in the given permutation
            for (Integer i : adj[v]) {
 
                // if the current node equals to
                // current element of permutation
                if (i == Perm[counter])
                    DFS(i, Perm);
            }
        }
    }
 
    // Returns true if P[] is a valid DFS of given
    // graph. In other words P[] can be obtained by
    // doing a DFS of the graph.
    static boolean checkPermutation(int N, int M, int[][] V,
                                    int P[])
    {
        // Create the required graph with
        // N vertices and M edges
        Graph G = new Graph(N);
 
        // Add Edges to Graph G
        for (int i = 0; i < M; i++)
            G.addEdge(V[i][0], V[i][1]);
 
        for (int i = 0; i < N; i++)
            mp.put(P[i], i);
 
        // Sort every adjacency
        // list according to HashMap
        for (int i = 1; i <= N; i++)
            G.adj[i].sort((a, b) -> a - b);
 
        // Call DFS with source node as P[0]
        G.DFS(P[0], P);
 
        // If Flag has been set to 1, means
        // given permutation is obtained
        // by DFS on given graph
        return flag;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Number of vertices
        // and number of edges
        int N = 3, M = 2;
 
        // Vector of pair to store edges
        int[][] V = { { 1, 2 }, { 2, 3 } };
        int P[] = { 1, 2, 3 };
 
        // Return the answer
        if (checkPermutation(N, M, V, P))
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}
 
// This code is contributed by jainlovely450

# Python3 program to check if given
# permutation can be obtained
# upon DFS traversal on given graph
flag = True
 
def addEdge(adj, u, v):
     
    # Add v to u’s list.
    adj[u].append(v)
     
    # Add u to v's list
    adj[v].append(u)
 
    return adj
 
# DFS traversal of the
# vertices reachable from v.
def DFS(adj, v, Perm):
     
    global mp,counter, flag
     
    # Increment counter for
    # every node being traversed
    counter += 1
 
    # Check if counter has
    # reached number of vertices
    if (counter == V):
         
        # Set flag to 1
        flag = 1
        return
 
    # Recur for all vertices adjacent
    # to this vertices only if it
    # lies in the given permutation
    for i in adj[v]:
         
        # If the current node equals to
        # current element of permutation
        if (counter<len(Perm) and i == Perm[counter]):
            DFS(adj, i, Perm)
 
# Returns true if P[] is a valid DFS of given
# graph. In other words P[] can be obtained by
# doing a DFS of the graph.
def checkPermutation(N, M, V, P):
     
    global mp
 
    # Create the required graph with
    # N vertices and M edges
    G = [[] for i in range(N + 1)]
 
    # Add Edges to Graph G
    for i in range(M):
        G = addEdge(G, V[i][0], V[i][1])
 
    for i in range(N):
        mp[P[i]] = i
 
    # Sort every adjacency
    # list according to HashMap
    for i in range(1, N + 1):
        G[i] = sorted(G[i])
 
    # Call DFS with source node as P[0]
    DFS(G, P[0], P)
 
    # If Flag has been set to 1, means
    # given permutation is obtained
    # by DFS on given graph
    return flag
 
# Driver code
if __name__ == '__main__':
     
    mp = {}
     
    # Number of vertices
    # and number of edges
    N, M, counter = 3, 2, 0
 
    # Vector of pair to store edges
    V = []
 
    V.append([1, 2])
    V.append([2, 3])
 
    P = [1, 2, 3]
 
    # Return the answer
    if (checkPermutation(N, M, V, P)):
        print("YES")
    else:
        print("NO")
 
# This code is contributed by mohit kumar 29

<script>
 
// JavaScript program to check if given
// permutation can be obtained
// upon DFS traversal on given graph
let flag = true
 
function addEdge(adj, u, v){
     
    // Add v to u’s list.
    adj[u].push(v)
     
    // Add u to v's list
    adj[v].push(u)
 
    return adj
}
 
// DFS traversal of the
// vertices reachable from v.
function DFS(adj, v, Perm){
     
    // Increment counter for
    // every node being traversed
    counter += 1
 
    // Check if counter has
    // reached number of vertices
    if (counter == V){
         
        // Set flag to 1
        flag = 1
        return
    }
 
    // Recur for all vertices adjacent
    // to this vertices only if it
    // lies in the given permutation
    for(let i of adj[v]){
         
        // If the current node equals to
        // current element of permutation
        if (counter<Perm.length && i == Perm[counter])
            DFS(adj, i, Perm)
    }
}
 
// Returns true if P[] is a valid DFS of given
// graph. In other words P[] can be obtained by
// doing a DFS of the graph.
function checkPermutation(N, M, V, P){
 
    // Create the required graph with
    // N vertices and M edges
    let G = new Array(N+1).fill(0).map(()=>new Array())
 
    // Add Edges to Graph G
    for(let i=0;i<M;i++)
        G = addEdge(G, V[i][0], V[i][1])
 
    for(let i=0;i<N;i++)
        mp.set(P[i] , i)
 
    // Sort every adjacency
    // list according to HashMap
    for(let i=1;i< N + 1;i++){
        G[i].sort()
    }
    // Call DFS with source node as P[0]
    DFS(G, P[0], P)
 
    // If Flag has been set to 1, means
    // given permutation is obtained
    // by DFS on given graph
    return flag
}
 
// Driver code
let mp = new Map()
 
// Number of vertices
// and number of edges
let N = 3,M = 2,counter = 0
 
// Vector of pair to store edges
let V = []
 
V.push([1, 2])
V.push([2, 3])
 
let P = [1, 2, 3]
 
// Return the answer
if (checkPermutation(N, M, V, P))
    document.write("YES","</br>")
else
    document.write("NO","</br>")
 
// This code is contributed by shinjanpatra
 
</script>

YES