Atividades

Problema obtido das provas de seleção das Olimpíadas Nacionais de Informática (ONI) de 2022 (deve ser consultado o endereço incluso):

"Nos concursos de programação universitários os concorrentes participam em grupos de exatamente três concorrentes. Na Universidade das ONI há N alunos que querem competir em concursos de programação, onde N é um múltiplo de 3, sendo que os alunos são identificados por inteiros consecutivos entre 1 e N.

Infelizmente, existem exatamente N-1 conflitos entre alunos, formando aquilo que pode ser visto como um grafo de conflitos, onde existe uma ligação entre um par de alunos (a,b) se esses dois alunos têm um conflito. Sabe-se que este grafo é conexo (ou seja, há um caminho entre qualquer par de alunos) e não contém qualquer ciclo (um caminho que começa e termina no mesmo aluno).

Podemos por exemplo ter 6 alunos e os seguintes conflitos: (2,1), (2,3), (4,3), (4,5) e (6,1), que formariam o grafo da figura seguinte:

Queremos formar equipas de exatamente 3 elementos de forma a que cada aluno esteja em exatamente uma equipa e que não haja qualquer conflito entre membros de uma equipa. Para o exemplo da figura anterior, poderíamos por exemplo formar duas equipas: uma com os alunos 1 3 5 e outra com os alunos 2 4 6.

O Problema

Dados N - 1 conflitos, determina se é possível formar equipas que satisfazem esta condição e se sim indica uma possível distribuição de equipas".

Problem obtained from the 2022 National Computer Olympics (ONI) selection tests:

"In university programming competitions, competitors participate in groups of exactly three competitors. At the University of ONI there are N students who want to compete in programming competitions, where N is a multiple of 3, and students are identified by consecutive integers between 1 and N.

 

Unfortunately, there are exactly N-1 conflicts between students, forming what can be seen as a conflict graph, where there is a connection between a pair of students (a,b) if these two students have a conflict. It is known that this graph is connected (that is, there is a path between any pair of students) and does not contain any cycle (a path that starts and ends at the same student).

 

We can, for example, have 6 students and the following conflicts: (2,1), (2,3), (4,3), (4,5) and (6,1), which would form the graph in the following figure:

 

 

We want to form teams of exactly 3 elements so that each student is in exactly one team and that there is no conflict between team members. For the example in the previous figure, we could, for example, form two teams: one with students 1 3 5 and another with students 2 4 6.

 

The problem

 

Data N - 1 conflicts, determines whether it is possible to form teams that satisfy this condition and, if so, indicates a possible distribution of teams."