Hallar la Transpuesta de un Grafo
Dado un grafo dirigido con
v vértices y e aristas, se te pide encontrar su transpuesta.La transpuesta de un grafo dirigido es un grafo que se obtiene al invertir la dirección de todas sus aristas. En otras palabras, es un grafo en el que todas las aristas dirigidas del grafo original están invertidas.
La transpuesta de un grafo es útil para encontrar rutas inversas o relaciones inversas en el grafo. Veremos algunas aplicaciones más adelante en el curso.
Entrada
La primera línea de la entrada contiene dos enteros
v (1 ≤ v ≤ 100 000) y e (1 ≤ e ≤ 100 000).Las siguientes
e líneas contienen pares de enteros v1, v2 (1 ≤ v1, v2 ≤ v) que indican que el vértice v1 está conectado con el vértice v2.Salida
El programa debe imprimir la lista de adyacencia del grafo complemento. Cada fila debe comenzar con el identificador de un vértice seguido de un punto y coma (
:) y luego sus conexiones. Las conexiones en cada fila deben estar separadas por un espacio. El orden tanto de los vértices como de las conexiones puede variar.Ejemplos
Entrada | Salida |
4 4
1 2
1 4
2 4
3 4 | 1:
2: 1
3:
4: 1 2 3 |
Constraints
Time limit: 3.5 seconds
Memory limit: 512 MB
Output limit: 1 MB