As notas da Tarefa 1 já estão no paca.
Infelizmente, os casos de teste do Spoj pra esse problema estavam muito ruins e várias soluções erradas foram aceitas... Nesses casos, junto com a explicação do erro coloquei um caso de teste que quebra a solução. Explico melhor os casos mais abaixo.
Não sei se isso vai acontecer de novo (espero que não), mas tentem pensar se a ideia está certa mesmo antes de mandar.
Várias pessoas fizeram o código de criação do grafo exatamente como no site do Feofiloff, alocando e liberando o grafo e sua matriz de adjacência a cada instância da entrada. Isso está certo e é o jeito mais bonito de fazer, mas a alocação leva muito tempo e como os casos de teste tem várias instâncias diferentes, alguns programas receberam 'limite de tempo excedido' por isso. Usar 'int adj[MAX_V][MAX_V]' na estrutura em vez de 'int ** adj' fez com que esses programas passassem no tempo. (essas soluções foram consideradas como corretas)
Algumas pessoas usaram o termo 'grafo' no sentido de 'componente' nos comentários do código. Cada instância é representada por um único grafo (uma única estrutura), o que pode acontecer é haver mais de uma componente (pedaços independentes do grafo).
Erros mais comuns (que estranhamente foram aceitos pelo Spoj):
Coloração gulosa: Olhar os vértices (ou arestas) em ordem e decidir direto em que lado colocar o vértice atual.
Ex: (possivel - ideia gulosa coloca 1 e 2 da mesma cor)
4 3
1 3
2 4
3 4
Propagação gulosa: Marcar o primeiro vértice e percorrer todos em ordem colorindo apenas vértices com vizinhos já coloridos. (alguns vértices ficam sem cor)
Ex: (impossivel - percorrendo as arestas em ordem 2 e 3 nunca são coloridos)
7 7
1 6
1 7
2 3
2 4
3 5
4 6
5 7
Verificação apenas de triângulos: é impossível bicolorir qualquer ciclo de tamanho ímpar, não apenas triângulos.
Ex: (impossivel)
5 5
1 2
2 3
3 4
4 5
5 1
Verificação apenas da componente do vértice 1: Fazer a chamada recursiva apenas a partir do primeiro vértice.
Ex: (impossivel - primeira componente é bicolorível)
5 4
1 2
3 4
4 5
5 3
Apenas uma chamada recursiva por nível: Ao fazer uma chamada recursiva para um vizinho do vértice atual, devolver a resposta direto sem olhar para os outros vizinhos
Ex: (possivel - no caso os vértices 1 e 2 são coloridos, mas a recursão não é chamada pro 5, o que faz com que o algoritmo trate o vértice 3 como início de uma segunda componente e use a mesma cor que para o vértice 1)
5 4
1 2
5 1
5 4
3 4
Acho que é isso. Qualquer dúvida ou reclamação, me mandem um e-mail.