Two parties are planned B and P The attendees are a set of n

Two parties are planned (B and P). The attendees are a set of n friends, F = {f1, f2...fn}. Among the friends are various pairs that don\'t like each other. Given a set of enemy pairs E = {(fi1, fj1,)...(fim, fjm)}, decide whether the friends in F can be partitioned into two parts B and P so that no pair from E appears together in B and P (each friend is in either P or B but not both and both parties will avoid conflict). Give an O(m+n) algorithm that either finds a partition of F into B and P so that for every (fir, fjr) E, |B (fir, fjr)| = 1 and |P (fir, fjr)| = 1 or determines that no such partition exists. A proof of correctness and runtime would be helpful for any algorithm that isn\'t BFS, DFS, dijkstra\'s. To clarify n is the number of friends and m is the number of enemy pairs.

Solution

if

(x,y) is in E we consider an edge between x and y

we want to tell if graph is bipartite or not

if it is find the two sets of bipartite graph

graph is bipartite if and only if there is no odd cycle

So the edges (enemy pairs) should not frm an odd cycle.

USE BFS

(before start represent emeny pairs as linked lists

linked list of a member will include all his enemies)

Now

start with any member call it source

1. Assign RED color to the source member (putting into set B).
2. Color all the enemies with BLUE color (putting into set P).
3. Color all enemies\' enemies with RED color (putting into set B).
4. This way, assign color to all members.
5. While assigning colors, if we find a enemy which is colored with same color as current member, then the members cannot be colored with 2 colors (or graph is not Bipartite)

If this process stops but there are still members which are not traced(colored)

Repeat the process with some other source not colored