RIO1 - Editorial

editorial
graph
graphs
rio1

#1

PROBLEM LINK:

Practice

Author: Vishal Khopkar

DIFFICULTY:

EASY

PREREQUISITES:

Graphs, sorting

PROBLEM:

RIO Olympics 2016 is hosting a team event where n teams are segregated into k groups such that n%k=0 and each group contains n/k teams. You’ve been given a partial schedule of the tournament and job is to segregate the teams into k different groups. However, neither n nor k has been directly given to you. What has been given is the partial schedule of x matches. With the help of this schedule, you need to print the teams segregated into different groups in alphabetical order. Also print the two groups by printing the group which contains the alphabetically first team first. Although the schedule is partial, it contains at least one match of each team.

EXPLANATION:

Read each line of the schedule and form a graph accordingly. Draw an edge between two teams if there is a match between them. For example, if the first match is BRAZIL vs ARGENTINA, there would be an edge between Brazil and Argentina in the graph. For more explanation, you can see the image in the link :

Image

Hence, just see the number of connected components in that graph.
However, you need to see that there are equal number of teams in each group. Hence, you may need to merge a few connected components to make a group.

SOLUTION

Thanking Mr. Manas Kumar Varma for the solution

Solution