teddy online judge |
|
|
teddy es un oso de peluche |
Datos invalidos
95. Un Algoritmo Mágico
Limite de tiempo : 6 seg. Total runs : 7 Aceptados : 2
| Límite de tiempo | Límite de memoria | Archivo de entrada | Archivo de salida |
|---|---|---|---|
| 6s | 64Mib | data.in | data.out |
Cada vez, las computadoras nos ayudan a resolver más problemas, pero existen problemas que son inherentemente difíciles de resolver en poco tiempo. Afortunadamente, se sabe para la mayoría de los problemas si pueden ser resueltos eficientemente o no. Este no es el caso del problema que vamos a analizar el día de hoy: el isomorfismo de grafos. Sabemos que este problema se encuentra en NP, pero no se sabe si es NP-completo o es solo P, lo que significa que se conoce un algoritmo algo lento que lo resuelve, pero no estamos seguros si exista uno más eficiente. Veamos si durante estas cinco horas logras descubrir un algoritmo mágico :)
El problema es el siguiente: dados dos grafos G y G′ con el mismo número de vértices y aristas, encuentra si es existe una función f tal que se cumpla que exista un arco de f(a) a f(b) en G′ si y solo si existe un arco de a a b en G. Dicho de otra manera, si es posible reacomodar los nombres a los vértices de G′ para que el grafo sea idéntico a G. De una manera más gráfica, si dibujas ambos grafos y su forma es idéntica, entonces son isomorfos.
Entrada
La primer línea de la entrada contiene un entero Nc (1 ≤ Nc ≤ 100), que contiene el número de casos de prueba. La primer línea de cada caso de prueba contiene un entero n (2 ≤ n ≤ 10,000), el número de vértices en los grafos. Las siguientes n-1 líneas contienen dos enteros a y b (1 ≤ a < b ≤ n), que indican que hay un arco de a a b en G. Las siguientes n-1 líneas contienen dos enteros a y b (1 ≤ a < b ≤ n), que indican que hay un arco de a a b en G′. Se garantiza que ambos grafos son conexos (i.e., puedes llegar de cualquier vértice a cualquier otro).
Salida
Para cada caso de prueba, imprime una línea con el número del caso, seguido de "Isomorfos" si los grafos son isomorfos, o "No-isomorfos" si no lo son. Sigue el formato de ejemplo.
Entrada/Salida de ejemplo
2 3 1 2 2 3 1 3 1 2 4 1 2 1 3 1 4 1 2 2 3 3 4 |
Caso 1: Isomorfos Caso 2: No-isomorfos |