Want to try solving this problem? You can submit your code online if you log in or register.

It has been many years since King Arthur has held a meeting for the Knights of the Round Table. Despite his best efforts to arrange seating in order to minimise conflict between knights, the last meeting deteriorated into a chaos of insulting and duelling unfit for the honourable dining room of Camelot.

Arthur must bring his knights together again, for rumour has spread throughout the kingdom that the dragons are becoming restless. In order to avoid the disasters of the last meeting, Arthur has decided to hold two meetings instead of one, and ensure that no two knights who would likely duel each other are invited to the same meeting. Furthermore, since immediate anti-dragon action is required, Arthur would like to have as many knights as possible at the first meeting.

After making a long list of all the knights and all the pairs of knights who may duel if invited to the same meeting, Arthur has requested you as the Court Informatician to write a program determining the largest number of knights that can be invited to the first meeting such that no pair of knights likely to duel each other are invited to the same meeting. Merlin, in his infinite wisdom, has assured you that there is at least one way of dividing all the knights into two meetings without any chance of duelling at either meeting.

Your program should read from the file `arthin.txt`.

- The first line of input will contain N, the number of knights.
- The second line of input will contain P, the number of pairs of duel-prone knights.
- Each of the following P lines will contain two space-separated integers
a and b, representing two knights who cannot be invited to the same meeting. It is guaranteed that
a b and that the same pair will not appear twice in the input. Knights are labelled from 1 to N.

Your program should write to the file `arthout.txt`. It should
output a single integer: the maximum number of knights that can be invited to
the first meeting without any chance of a duel occurring at either the first or
second meeting.

8 6 1 2 1 5 3 2 5 3 6 8 7 6

5

In this example, Arthur can invite knights 2, 4, 5, 7 and 8 to the first meeting and knights 1, 3 and 6 to the second meeting. There is no way for Arthur to invite more than 5 knights to the first meeting without risking the chance of a duel between knights, so 5 is the correct answer.

To evaluate your solution, the judges will run your program against several different input files. All of these files will adhere to the following bounds:

- 1 ≤ N ≤ 100,000
- 0 ≤ P ≤ 1,000,000

As some of the test cases will be quite large, you may need to think about how well your solution scales for larger input values. However, not all the cases will be large. In particular:

- For 20% of cases, N ≤ 20.

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.

Privacy
statement

© Australian Mathematics Trust 2001-2022

Page generated: 16 August 2022, 5:54am AEST