1. Problem

  BOJ_2516 is the problem solved by a naive solution. The level of problem is Platinum 4.(Link of the problem of BOJ)

Inputs

  • The number of monkeys $N (3 \leq N \leq 100,000)$
  • $N$ rows: The number of hostile monkeys of the $i$th monkey, the indices of hostile monkeys

Conditions

  • The maximal number of hostile monkeys of a monkey is 3.
  • We have to put monkeys in the two cages under the conditions below.
  • Condition 1: For each monkey, there is not more than one hostile monkey in the same cage.
  • Condition 2: There is no empty cage.

Outputs

  • Two rows: The number of monkeys in a cage, the indices of monkeys in the cage.

Time & Space Limit

  • Time limit: 1 sec
  • Space limit: 128MB



2. Solve the problem: Naive solution

  I try to apply lots of greedy solution to this problem. But there is no correct greedy solution. This problem can be solved by naive algorithm.

  1. Put all monkeys in the same cage.
  2. Check all monkeys. If there are more than two hostile monkeys of the monkey which is been checking in the same cage, the monkey is moved to another cage.
  3. After all iteration, if there is an empty cage, move any monkey in another cage to the empty cage.

  Run the function above until there is no more monkey which have to be moved. Because he maximal number of hostile monkeys of a monkey is 3, the ‘move’ operation occurs lower than $3N$ times.
  In implementation, the relationship of monkeys is converted to a graph. Monkeys are vertices, and Hostile relationship between the $i$th monkey and the $j$th monkey is the edge of vertices labeled $i$ and $j$. Because there are up to 100,000 monkeys, Adjacency Matrix Graph Representation can not be used. So, I used Adjacency List Graph Representation. Actually, the latter is more efficient, because the number of edges is $O(N)$.



3. Source Code

You can watch the source code clearly in this github link.



Refers

gcmange, “[BOJ 2516] 원숭이”