Olá... no problema Is it a tree? Eu posso ter duas árvores no mesmo caso de teste?
Por exemplo:
1 2 2 3
4 5 5 6 0 0
-1 -1
Pode sim.
Ou melhor, entenda cada caso como um digrafo, que pode ser disconexo.
Você que deverá dizer se se trata de uma árvore ou não.
No seu exemplo, você deverá dizer que não se trata de uma árvore.
Ou melhor, entenda cada caso como um digrafo, que pode ser disconexo.
Você que deverá dizer se se trata de uma árvore ou não.
No seu exemplo, você deverá dizer que não se trata de uma árvore.
Eu rodei todos os exemplos do enunciado do problema "Is It A Tree?" e todos retornaram certo... Mas rodo no UVa e recebo wrong answer... E olha que já briguei bastante com ele e só recebo wrong answer...
Eu estou afirmando alguma coisas:
1 - Só pode ter 1 root.
2 - O digrafo tem menos de 100000 (cem mil) vértices.
3 - Vazio é uma árvore.
4 - Se eu receber de entrada um vértice inválido eu descarto.
Algo desses itens está errado?
Eu estou afirmando alguma coisas:
1 - Só pode ter 1 root.
2 - O digrafo tem menos de 100000 (cem mil) vértices.
3 - Vazio é uma árvore.
4 - Se eu receber de entrada um vértice inválido eu descarto.
Algo desses itens está errado?
Carlos,
Para testar se um grafo é uma árvore, você precisa testar exatamente as três condições do enunciado:
1 - Exatamente 1 root.
2 - Todos os nós que não forem o root só podem ter um vértice apontando para eles.
3 - Tem exatamente um caminho (único) do root para cada outro nó.
Sua afirmação dois é equívocada, já que o problema não diz nada à respeito do número de vértices. No entanto, como o Leonardo apontou em outro post, se você assumir que não há mais de 50000 vértices, você consegue passar o problema. Quanto à afirmação 4, não há vértices inválidos na entrada.
Para testar se um grafo é uma árvore, você precisa testar exatamente as três condições do enunciado:
1 - Exatamente 1 root.
2 - Todos os nós que não forem o root só podem ter um vértice apontando para eles.
3 - Tem exatamente um caminho (único) do root para cada outro nó.
Sua afirmação dois é equívocada, já que o problema não diz nada à respeito do número de vértices. No entanto, como o Leonardo apontou em outro post, se você assumir que não há mais de 50000 vértices, você consegue passar o problema. Quanto à afirmação 4, não há vértices inválidos na entrada.
Oi Lucas,
Eu achei o problema... Achei um contra exemplo que passou, agora que ajeitei o programa o Sr.UVa me liberou... =)
Abaixei o max para 50000 vértices e passou também.
Valeu pela ajuda.
Eu achei o problema... Achei um contra exemplo que passou, agora que ajeitei o programa o Sr.UVa me liberou... =)
Abaixei o max para 50000 vértices e passou também.
Valeu pela ajuda.
Marcos,
Como eu já havia falado, só vai haver um caso de teste. O Online Judge vai rodar seu programa com uma entrada que possui inúmeros casos. Pense que a "Simple Input" do problemas está toda em apenas um arquivo, e seu programa vai ser rodado exatamente assim:
$./a.out < simple_input
O que fazemos para testar o programa é extamente isso... colocamos a Simple Input do jeito que é dado em um arquivo e rodamos ele como acabei de mostrar, e comparamos com a saída esperada.
O exemplo que vc deu possui apenas uma arvore, mas se tivessemos, por exemplo:
1 2 2 3 0 0
4 5 5 6 0 0
-1 -1
Seu programa deveria responder:
Case 1 is a tree.
Case 2 is a tree.
Como eu já havia falado, só vai haver um caso de teste. O Online Judge vai rodar seu programa com uma entrada que possui inúmeros casos. Pense que a "Simple Input" do problemas está toda em apenas um arquivo, e seu programa vai ser rodado exatamente assim:
$./a.out < simple_input
O que fazemos para testar o programa é extamente isso... colocamos a Simple Input do jeito que é dado em um arquivo e rodamos ele como acabei de mostrar, e comparamos com a saída esperada.
O exemplo que vc deu possui apenas uma arvore, mas se tivessemos, por exemplo:
1 2 2 3 0 0
4 5 5 6 0 0
-1 -1
Seu programa deveria responder:
Case 1 is a tree.
Case 2 is a tree.
Lucas (ou alguem =o] )
Por que, no exemplo original do Marcos:
1 -> 2 -> 3
4 -> 5 -> 6
Voce disse que era uma arvore ? pra mim, isso tem dois roots (1 e 4)...
ou isso (dois digrafos disjuntos) tambem eh um arvore ?
Obrigado!
Por que, no exemplo original do Marcos:
1 -> 2 -> 3
4 -> 5 -> 6
Voce disse que era uma arvore ? pra mim, isso tem dois roots (1 e 4)...
ou isso (dois digrafos disjuntos) tambem eh um arvore ?
Obrigado!
Eu quis dizer que o exemplo do Marcos possuía apenas um teste, apenas uma "possível" árvore a ser testada, só escrevi errado. Como o Leonardo já havia dito, e você ressaltou, o exemplo dele não é uma árvore, pois além de possuir dois roots, não há caminho de nenhum dos roots para todos os nós (ele é disconexo).
Isso era tudo que eu queria sabe... valew! ^^
Beleza! Era so pra ter certeza =) Valeu!
Agora, ainda falta alguma coisa, pq o UVa ainda insiste que meu EP esta errado.
Tem mais algum caso patologico que voces enxergam nisso?
Agora, ainda falta alguma coisa, pq o UVa ainda insiste que meu EP esta errado.
Tem mais algum caso patologico que voces enxergam nisso?
Pra quem não quer pensar, ou já cansou de pensar, casos particulares:
Árvore vazia é uma árvore.
Grafos disjuntos nunca formam uma árvore.
Não se esqueçam que os grafos podem ter loops, ou seja, uma aresta com início e fim no mesmo vértice. Um grafo com loop nunca pode ser uma árvore.
Árvore vazia é uma árvore.
Grafos disjuntos nunca formam uma árvore.
Não se esqueçam que os grafos podem ter loops, ou seja, uma aresta com início e fim no mesmo vértice. Um grafo com loop nunca pode ser uma árvore.
Quando no meu arquivo só tem:
0 0
-1 -1
é uma árvore vazia e portanto é uma árvore?
0 0
-1 -1
é uma árvore vazia e portanto é uma árvore?
exatamente!
Eu considerei que grafos disjuntos não são uma árvore. Infelizmente não consegui submeter meu código ainda, parece que o site esta em manutenção ^.^.
Para alguém que já passou o problema, como tratou esse caso?
Abraços
Para alguém que já passou o problema, como tratou esse caso?
Abraços
Fabricio,
Grafos disjuntos nunca satisfazem a condição de existir exatamente um caminho do root para todos os outros nós. Para verificar isso, basta aplicar um algoritmo de busca à partir do root e verificar que você não visitou todos os nós do grafo.
Grafos disjuntos nunca satisfazem a condição de existir exatamente um caminho do root para todos os outros nós. Para verificar isso, basta aplicar um algoritmo de busca à partir do root e verificar que você não visitou todos os nós do grafo.
De fato. Eu fiz um pouco diferente disso. Como eu montei a arvore com apontadores para os pais (invertendo os pares da entrada) eu garanti durante a construção que só haveria uma raiz, e depois, para cada nó garanti que havia um caminho dele para a raiz, ou que ele chegava em algum outro nó com caminho para raiz. No meu caso, não dá para disparar uma busca partindo da raiz.
Eu ainda não estou certo se minha idéia é mais ou menos eficiente do que a solução que você propos, mas como eu garanto passar por cada nó apenas uma vez, acho que deve ser equivalente. Pelo menos a uva gostou ^.^.
Eu ainda não estou certo se minha idéia é mais ou menos eficiente do que a solução que você propos, mas como eu garanto passar por cada nó apenas uma vez, acho que deve ser equivalente. Pelo menos a uva gostou ^.^.
Opa Fabrício,
Grafo disjunto não é uma árvore mesmo... Pelo menos foi assim que eu tratei e passou... =)
Grafo disjunto não é uma árvore mesmo... Pelo menos foi assim que eu tratei e passou... =)