Here’s an algorithmic way to do this.

We can associate a directed graph by assigning a vertex to each person and placing a directed edge from i to j if i has a grudge against j. So each vertex has exactly one outgoing edge.

First,

pick a vertex and follow its child vertex. Since every vertex has an outgoing edge, we can always find a child vertex, and since there are finitely many vertices, we must revisit a vertex. In other words, there’s a cycle in every connected component.

Next,

pick a connected component and pick a vertex v0 in a cycle in that component. Call it level 0. Place any parent vertex of v0 in level 1. And so on. This way, there is no edge within a level. In particular, a vertex at level k has an outgoing edge to some vertex at level k-1, except for v0, which has an outgoing edge to exactly one vertex in some level l>0. If l is odd, we can colour the vertices with two colours, alternating every level. Else, use two colours up to level l-1, then use a third colour at level l, and then continue using the first two colours from level l+1 and above.

Repeat the above algorithm for all connected components.

Here’s an algorithmic way to do this.

We can associate a directed graph by assigning a vertex to each person and placing a directed edge from i to j if i has a grudge against j. So each vertex has exactly one outgoing edge.

First,

pick a vertex and follow its child vertex. Since every vertex has an outgoing edge, we can always find a child vertex, and since there are finitely many vertices, we must revisit a vertex. In other words, there’s a cycle in every connected component.

Next,

pick a connected component and pick a vertex v0 in a cycle in that component. Call it level 0. Place any parent vertex of v0 in level 1. And so on. This way, there is no edge within a level. In particular, a vertex at level k has an outgoing edge to some vertex at level k-1, except for v0, which has an outgoing edge to exactly one vertex in some level l>0. If l is odd, we can colour the vertices with two colours, alternating every level. Else, use two colours up to level l-1, then use a third colour at level l, and then continue using the first two colours from level l+1 and above.

Repeat the above algorithm for all connected components.

Added: Here’s an example diagram depicting the result of above algorithm when l=2. The cycle in this connected component is shown in red.

Here’s an algorithmic way to do this.

We can associate a directed graph by assigning a vertex to each person and placing a directed edge from i to j if i has a grudge against j. So each vertex has exactly one outgoing edge.

Pick a vertex v0 and consider it to be level 0. Place any vertex that has grudge against v0 in level 1. And so on. This way, there is no edge within a level. In particular, a vertex at level k has a grudge against some vertex at level k-1, except for v0, which has a grudge against exactly one vertex in some level l below. If l is odd, we can colour the vertices with two colours, alternating every level. Else, use two colours up to level l-1, then use a third colour at level l, and then continue using the first two colours from level l+1 and above.

If there are any leftover vertices, repeat the same algorithm as above for their connected components.

Here’s an algorithmic way to do this.

We can associate a directed graph by assigning a vertex to each person and placing a directed edge from i to j if i has a grudge against j. So each vertex has exactly one outgoing edge.

First,

pick a vertex and follow its child vertex. Since every vertex has an outgoing edge, we can always find a child vertex, and since there are finitely many vertices, we must revisit a vertex. In other words, there’s a cycle in every connected component.

Next,

pick a connected component and pick a vertex v0 in a cycle in that component. Call it level 0. Place any parent vertex of v0 in level 1. And so on. This way, there is no edge within a level. In particular, a vertex at level k has an outgoing edge to some vertex at level k-1, except for v0, which has an outgoing edge to exactly one vertex in some level l>0. If l is odd, we can colour the vertices with two colours, alternating every level. Else, use two colours up to level l-1, then use a third colour at level l, and then continue using the first two colours from level l+1 and above.

Repeat the above algorithm for all connected components.