1st Balkan Olympiad on Informatics
Constantza, Romania, 24-29 May 1993

Day 2 - Problem 1 (30 points)



Imagine you are at the social get-together with at most 500 guests. The host invites you all to have dinner. There are several tables in the dining room. The way the guests sit down at the tables is the following: each one sitting not alone at a certain table must know at least one person sitting at the same table and no one else sitting at other tables.

It is supposed that if a person knows a second person, the second one knows the first person too. No one introduces himself to the other persons sitting at the same table. That means that if two persons are sitting at the same table, but initially they do not know each other, they will not know each other afterwards either.

Determine how many tables are necessary and the persons sitting at each table (20 points). At each table there is only one person who will talk to the waiter; he/she is called the leader of the table. Each person relays his wishes concerning the menu to the persons he knows. The time allocated to each person to relay his wishes to each person he knows is supposed to be the same for each person.

Determine the most suitable person as leader of the table in order to receive information from all the persons sitting at the table in the shortest possible period of time; produce at output the leader of each table and the corresponding period of time(20 points). Afterwards, the host wishes to unify tables. For this purpose, he calls some friends. Each of them, when coming, is introduced to the leaders of two tables, links the tables, sits down at the new formed table and becomes the leader of this table.

What is the order of linking the tables in this way, so that at last all tables unified into a single one and the conditions of the previous point are satisfied? Specify the minimum necessary period of time for the leader to get information from all the other persons. (30 points)
After the complete linking, the friends of the host are leaving and the tables get their initial structure until the end of the dinner. When the dinner is over, the persons start leaving the tables.

Determine, for each table, the minimum number of persons and the order in which they are leaving the table, until the persons who are still at the table do not know each other. (30 points)

Example:
Suppose the number of persons is 8 and:
- person 1 knows persons 2 and 3;
- person 2 knows persons 1 and 4;
- person 3 knows persons 1 and 4;
- person 4 knows persons 2 and 3;
- person 5 knows person 6;
- person 6 knows persons 5 and 7;
- person 7 knows person 6;
- person 8 does not know other persons;



  • A valid input is:
    8
    1 2
    1 3
    2 4
    7 6
    4 3
    5 6
    0 0
  • A valid output is:
    1st point:There are 3 tables Table 1: 1 2 3 4
    Table 2: 5 6 7
    Table 3: 8
    2nd point:Leaders Table 1: 2
    Table 2: 6
    Table 3: 8
    3rd point 6 8 New leader: 9
    2 9 New leader: 10
    Period of time: 3
    Persons leaving Table 1: 2 3
    Table 2: 6
    Table 3: