Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CORDAISG - Grafos cordais

Sabe-se que certos problemas que são NP-completos para grafos genéricos podem ser resolvidos em tempo polinomial para certas classes especiais de grafos. Um problema importante em computação teórica é identificar quando um grafo pertence a determinada classe, justamente para sabermos quando podemos resolver certo problema em tempo polinomial.

Neste problema, pede-se para verificar se determinado grafo pertence a classe dos grafos cordais. Em grafos cordais, problemas como o do clique máximo podem ser resolvidos em tempo polinomial. Um grafo cordal é um grafo em que qualquer sub-ciclo com mais de 3 vértices possui uma corda, ou seja, uma aresta do grafo que não pertence ao ciclo mas liga dois vértices não adjacentes no ciclo.

Entrada

A entrada contém diversos casos de teste. Após o último caso de teste da entrada teremos uma linha contendo 0 0.

A primeira linha de um caso de teste contém dois inteiros, n e m , indicando o numero de vértices e arestas, respectivamente, 1≤n≤1000. Após isso, segue-se m linhas contendo u (1≤u≤n) e v(1≤v≤n), descrevendo as arestas do grafo.

Saída

Para cada caso de teste, imprima '0', caso o grafo não seja cordal, e '1', caso o grafo seja cordal.

Exemplo

Entrada:
4 4
1 2
2 3
3 4
4 1
3 3
1 2
2 3
3 1
0 0 Saída: 01

Adicionado por:gogo40
Data:2009-11-29
Tempo limite:0.271s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP NODEJS OBJC PERL6 PY_NBC SCALA SQLITE TCL VB.NET

hide comments
2010-01-27 02:16:10 Marcos Daniel [UERN]
Ah entendi .. pensei que fosse o contrário ..
obg
2009-12-23 18:19:16 gogo40
Nesse problema, um grafo NĂO é cordal se ele tiver algum sub-ciclo com mais de 3 vértices que năo possui uma corda. Caso contrário, o grafo é cordal.
2009-12-12 01:44:53 Marcos Daniel [UERN]

Um grafo cordal é um grafo em que qualquer sub-ciclo com mais de 3 vértices possui uma corda, ou seja, uma aresta do grafo que năo pertence ao ciclo mas liga dois vértices năo adjacentes no ciclo.
Como pode a segunda saida ser '1' se o grafo tem apenas 3 vertices ???
2009-12-07 18:19:48 Davi Alves Magalhães [UERN]
A saída está correta? Acho que nos dois casos eles năo săo cordais.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.