Encontrar o Complemento de um Grafo
Dado um grafo não dirigido com
v vértices e e arestas, pede-se que encontres o seu complemento.O complemento de um grafo é um grafo que contém arestas entre todos os nós que não possuíam uma aresta no grafo original, ao mesmo tempo que não contém arestas entre nós onde o grafo original já tinha uma aresta.
.png?table=block&id=18b2c681-664d-8173-a5d5-efb97b6d2289&cache=v2)
Entrada
A primeira linha da entrada contém dois inteiros
v (1 ≤ v ≤ 500) e e (1 ≤ e ≤ 100 000).As seguintes
e linhas incluem pares de inteiros v1, v2 (1 ≤ v1, v2 ≤ v), indicando que o vértice v1 está ligado ao vértice v2, e vice-versa.Saída
O programa deve imprimir a lista de adjacências do grafo complementar. Cada linha deve começar com o id de um vértice seguido de dois-pontos (
:) e, em seguida, as suas conexões. As conexões de cada linha devem ser separadas por um espaço. A ordem dos vértices e a ordem das conexões podem ser arbitrárias.Exemplos
Entrada | Saída |
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