Trovare il complemento di un grafo
Dato un grafo non orientato con
v vertici e e archi, occorre trovare il suo complemento.Il complemento di un grafo è un grafo che possiede un arco fra tutti i nodi che non erano collegati fra loro nel grafo originale e, contemporaneamente, non presenta un arco fra i vertici che invece risultavano connessi nel grafo di partenza.
.png?table=block&id=18b2c681-664d-81f4-afcb-ca1de687ccaa&cache=v2)
Input
La prima riga dell’input contiene due interi
v (1 ≤ v ≤ 500) ed e (1 ≤ e ≤ 100 000).Le successive
e righe contengono coppie di interi v1, v2 (1 ≤ v1, v2 ≤ v), indicando che il vertice v1 è collegato al vertice v2 e viceversa.Output
Il programma deve stampare la lista di adiacenza del grafo complementare. Ogni riga deve iniziare con l’id di un vertice, seguito da due punti (
:) e poi dalle sue connessioni. Le connessioni in ogni riga devono essere separate da uno spazio. L’ordine dei vertici e delle connessioni può essere arbitrario.Esempi
Ingresso | Uscita |
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