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:
CPP
// 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
# 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)
Publicación traducida automáticamente
Artículo escrito por red_devil09 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA