Graph colouring algorithm: typical scheduling problem
- by newba
Hi,
I'm training code problems like UvA and I have this one in which I have to, given a set of n exams and k students enrolled in the exams, find whether it is possible to schedule all exams in two time slots.
Input
Several test cases. Each one starts with a line containing 1 < n < 200 of different examinations to be scheduled.
The 2nd line has the number of cases k in which there exist at least 1 student enrolled in 2 examinations. Then, k lines will follow, each containing 2 numbers that specify the pair of examinations for each case above.
(An input with n = 0 will means end of the input and is not to be processed).
Output:
You have to decide whether the examination plan is possible or not for 2 time slots.
Example:
Input:
3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0
Ouput:
NOT POSSIBLE.
POSSIBLE.
I think the general approach is graph colouring, but I'm really a newb and I may confess that I had some trouble understanding the problem.
Anyway, I'm trying to do it and then submit it.
Could someone please help me doing some code for this problem?
I will have to handle and understand this algo now in order to use it later, over and over.
I prefer C or C++, but if you want, Java is fine to me ;)
Thanks in advance
