Encontrar el complemento de un grafo
Dado un grafo no dirigido con
v vértices y e aristas, se te pide encontrar su complemento.El complemento de un grafo es otro grafo que tiene aristas entre todos los nodos que no estaban conectados en el original y, al mismo tiempo, no tiene aristas entre aquellos vértices que sí estaban conectados en el grafo original.
.png?table=block&id=18b2c681-664d-81b3-8377-fd4e6b6cd6d5&cache=v2)
Entrada
La primera línea de la entrada contiene dos enteros
v (1 ≤ v ≤ 500) y e (1 ≤ e ≤ 100 000).Las siguientes
e líneas contienen pares de enteros v1, v2 (1 ≤ v1, v2 ≤ v), lo que significa que el vértice v1 está conectado con el vértice v2 y viceversa.Salida
El programa debe imprimir la lista de adyacencia del grafo complemento. Cada fila debe iniciar con el id de un vértice seguido de un punto y coma (
:) y luego sus conexiones. Las conexiones en cada fila deben separarse por un espacio. El orden tanto de los vértices como de sus conexiones puede ser arbitrario.Ejemplos
Entrada | Salida |
4 4
1 2
4 2
4 1
3 4 | 1: 3
2: 3
3: 1 2
4: |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB