Problema C - Outro Tipo de Tesouro

No mundo real um tesouro é algo como ouro ou pedras preciosas, mas no mundo da matemática um tesouro é algo muito mais importante. É algo difícil de encontrar mesmo que saibamos que esteja lá. O nosso tesouro de hoje são cliques!

Vamos supor que temos um grafo com N vértices e M arestas. Um clique é um subconjunto de vértices que estão todos ligados entre si (ou seja, formam um grafo completo). É nos dado um inteiro X e o nosso objetivo é encontrar um clique de tamanho exatamente X. Este problema é muito díficil no geral, mas felizmente os grafos que vamos ter de considerar têm propriedades muito específicas.

O Problema

É nos dado um grafo com N vértices e M arestas assim como um inteiro X, o objetivo é encontrar um clique com X nós.

Input

Cada caso de teste começa com três inteiros separados por espaços, N, o número de vértices, M, o número de arestas, e X, o tamanho do clique pretendido.

Seguem-se M linhas, cada uma com dois inteiros separados por espaços de valores entre 1 e N representando arestas.

É garantido que não há multiplas arestas entre os mesmos dois vértices e que todas as arestas ligam vértices diferentes.

Casos de teste

Há 4 casos de teste, cada um com uma pontuação fixa (sem pontuações parciais para cada um). Devem olhar para cada caso de teste individualmente, os casos não são arbitrários e devem observar e aproveitar a estrutura de cada um para o resolver.

Os casos de teste são os seguintes:

• Caso 1: A valer 20 pontos, inp1.txt;

  Descrição: N = 10,000, M = 10,000, X = 3, o grafo é uma árvore com um único triângulo.

• Caso 2: A valer 25 pontos, inp2.txt;

  Descrição: N = 1,000, M = 10,000, X = 100, o grafo é um grafo aleatório (*) ao qual foi adicionado um clique com 100 vértices.

• Caso 3: A valer 25 pontos, inp3.txt;

  Descrição: N = 1,000, M = 10,000, X = 15, o grafo é um grafo aleatório (*) ao qual foi adicionado um clique com 15 vértices.

• Caso 4: A valer 30 pontos, inp4.txt;

  Descrição: N = 1,000, M = 50,000, X = 50, o grafo é um grafo qualquer que contém pelo menos um clique com 100 vértices.

(*) Um grafo aleatório com M arestas é um grafo onde cada aresta é escolhida com a mesma probabilidade. Uma outra forma de pensar no processo é considerar um conjunto com todas as N(N - 1)/2 possíveis arestas e tiramos M arestas de forma uniforme sem reposição.

Output/Submissão

Deve ser submetido um único ficheiro de txt (o formato é importante, o vosso ficheiro deve terminar em .txt). O ficheiro deve conter 4 linhas, uma por caso de teste, cada uma com os cliques pretendidos para o caso de teste, sendo que o formato por linha é o seguinte:

X inteiros distintos entre 1 e N separados por espaços, cada um representando um nó do clique. Podem vir por qualquer ordem.

Observações importantes:

• Caso não tenham solução para um dos casos de teste, têm de incluir uma linha vazia.
• Se algum dos outputs for inválido, seja porque não contém inteiros suficientes, ou porque os inteiros não estejam entre 1 e N ou haja inteiros repetidos ou não representem um clique, o resultado da submissão será Wrong Answer e terão 0 pontos nesse caso de teste.

Um exemplo válido de um ficheiro solução seria o seguinte (a sua pontuação é de 0 pontos):

1 2 3

1 2 3 ... 15
1 2 3 4 ... 50

Dicas para gerar o output

Visto que é necessário criar um ficheiro de txt para a vossa submissão, pode ser útil usar o terminal para gerar os ficheiros de texto (isto não é obrigatório, podem criar o ficheiro como quiserem).

Se para correrem o vosso programa usarem o comando X (por exemplo, para C++ isto seria algo como ./a.out, depois de compilar com g++ codigo.cpp), podem usar o seguinte comando para ler o input de um ficheiro inp.txt e escrever para um ficheiro out.txt: X < inp.txt > out.txt.

Para facilitar a organização do ficheiro de submissão, é aconselhado gerar um txt por cada caso de teste, por exemplo, para o caso de teste 2 ter um out2.txt.

Para posteriormente gerar um ficheiro out.txt para submeter, podem usar o seguinte comando (assumindo que têm um ficheiro outI.txt para cada um dos 4 casos de teste I): cat out1.txt > out.txt;cat out2.txt >> out.txt;cat out3.txt >> out.txt;cat out4.txt >> out.txt