Isomorfismo en árboles N-arios

Dados dos árboles N-arios que tienen M Nodes cada uno. También, dadas sus aristas y sus raíces respectivamente. La tarea es comprobar si son árboles isomorfos o no. Si ambos árboles son isomorfos, imprima «Sí» , de lo contrario, imprima «No» .
Ejemplos: 
 

Entrada: M = 9, Node raíz del árbol-1: 1, Node raíz del árbol-2: 3 
Bordes del árbol-1: { (1, 3), (3, 4), (3, 5), (1 , 8), (8, 9), (1, 2), (2, 6), (2, 7) } 
Bordes del árbol-2: { (3, 1), (1, 2), (1, 5), (3, 6), (6, 7), (3, 4), (4, 8), (4, 9) } 
 

Salida: SÍ
Entrada: M = 9, Node raíz del árbol-1: 6, Node raíz del árbol-2: 7 
Bordes del árbol-1: {(1, 3),(1, 2), (1, 8) , (3, 4), (3, 5), (8, 9), (2, 6), (2, 7)} 
Bordes del Árbol-2: {(1, 2), (1, 5), (3, 1), (3, 4), (4, 8), (4, 9), (6, 3), (7, 6)} 
 

Salida: NO 
 

Enfoque: 
La idea es encontrar la forma canónica de ambos árboles y compararlos. El Node hoja devolverá «()» a sus niveles superiores posteriores. 
A continuación se muestra el ejemplo que muestra el proceso de encontrar la forma canónica. 
 

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// To create N-ary tree
map<int, vector<int> > tree;
 
// Function which will accept the root
// of the tree and its parent (which
// is initially "-1") and will return
// the canonical form of the tree
string ConvertCanonical(int vertex,
                        int parent)
{
    // In this string vector we will
    // store canonical form of out
    // current node and its subtree
    vector<string> child;
 
    // Loop to the neighbours of
    // current vertex
    for (auto neighbour : tree[vertex]) {
 
        // This is to prevent us from
        // visiting the parent again
        if (neighbour == parent)
            continue;
 
        // DFS call neighbour of our
        // current vertex & it will
        // pushback the subtree-structure
        // of this neighbour into our
        // child vector.
        child.push_back(ConvertCanonical(
            neighbour, vertex));
    }
 
    // These opening and closing
    // brackets are for the
    // current node
    string str = "(";
 
    // Sorting function will re-order
    // the structure of subtree of
    // the current vertex in a
    // shortest-subtree-first manner.
    // Hence we can
    // now compare the two tree
    // structures effectively
    sort(child.begin(), child.end());
 
    for (auto j : child)
        str += j;
 
    // Append the subtree structure
    // and enclose it with "(" <subtree>
    // ")" the opening and closing
    // brackets of current vertex
    str += ")";
 
    // return the subtree-structure
    // of our Current vertex
    return str;
}
 
// Function to add edges
void addedge(int a, int b)
{
    tree[a].push_back(b);
    tree[b].push_back(a);
}
 
// Driver code
int main()
{
    // Given N-ary Tree 1
    addedge(1, 3);
    addedge(1, 2);
    addedge(1, 5);
    addedge(3, 4);
    addedge(4, 8);
    addedge(4, 9);
    addedge(3, 6);
    addedge(6, 7);
 
    // Function Call to convert Tree 1
    // into canonical with 3 is the root
    // and the parent of root be "-1"
    string tree1 = ConvertCanonical(3, -1);
 
    // Clearing our current tree
    // before taking input of
    // next tree
    tree.clear();
 
    // Given N-ary Tree 2
    addedge(1, 3);
    addedge(3, 4);
    addedge(3, 5);
    addedge(1, 8);
    addedge(8, 9);
    addedge(1, 2);
    addedge(2, 6);
    addedge(2, 7);
 
    // Function Call to convert Tree 2
    // into canonical
    string tree2 = ConvertCanonical(1, -1);
 
    // Check if canonical form of both
    // tree are equal or not
    if (tree1 == tree2)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
 
    return 0;
}

# Python3 program for the above approach
 
# To create N-ary tree
tree=dict()
 
# Function which will accept the root
# of the tree and its parent (which
# is initially "-1") and will return
# the canonical form of the tree
def ConvertCanonical(vertex, parent):
    # In this string vector we will
    # store canonical form of out
    # current node and its subtree
    child=[]
 
    # Loop to the neighbours of
    # current vertex
    for neighbour in tree[vertex] :
 
        # This is to prevent us from
        # visiting the parent again
        if (neighbour == parent):
            continue
 
        # DFS call neighbour of our
        # current vertex & it will
        # pushback the subtree-structure
        # of this neighbour into our
        # child vector.
        child.append(ConvertCanonical(
            neighbour, vertex))
     
 
    # These opening and closing
    # brackets are for the
    # current node
    s = "("
 
    # Sorting function will re-order
    # the structure of subtree of
    # the current vertex in a
    # shortest-subtree-first manner.
    # Hence we can
    # now compare the two tree
    # structures effectively
    child.sort()
 
    for j in child:
        s += j
 
    # Append the subtree structure
    # and enclose it with "(" <subtree>
    # ")" the opening and closing
    # brackets of current vertex
    s += ")"
 
    # return the subtree-structure
    # of our Current vertex
    return s
 
 
# Function to add edges
def addedge(a, b):
    if a in tree:
        tree[a].append(b)
    else:
        tree[a]=[b,]
    if b in tree:
        tree[b].append(a)
    else:
        tree[b]=[a,]
 
 
# Driver code
if __name__=='__main__':
    # Given N-ary Tree 1
    addedge(1, 3)
    addedge(1, 2)
    addedge(1, 5)
    addedge(3, 4)
    addedge(4, 8)
    addedge(4, 9)
    addedge(3, 6)
    addedge(6, 7)
 
    # Function Call to convert Tree 1
    # into canonical with 3 is the root
    # and the parent of root be "-1"
    tree1 = ConvertCanonical(3, -1)
 
    # Clearing our current tree
    # before taking input of
    # next tree
    tree.clear()
 
    # Given N-ary Tree 2
    addedge(1, 3)
    addedge(3, 4)
    addedge(3, 5)
    addedge(1, 8)
    addedge(8, 9)
    addedge(1, 2)
    addedge(2, 6)
    addedge(2, 7)
 
    # Function Call to convert Tree 2
    # into canonical
    tree2 = ConvertCanonical(1, -1)
 
    # Check if canonical form of both
    # tree are equal or not
    if (tree1 == tree2):
        print("YES")
    else:
        print("NO")

YES

Complejidad de tiempo: O(E * log(E)) , donde E es el número de aristas.
Espacio Auxiliar : O(E)