In this lab, you’ll investigate the ways graphs can model and solve problems.
You’re hosting a party. Unfortunately, many of your invitees are sworn enemies of each other. As the organizer, to ensure aggregate happiness, you’d like to separate the party-goers into two groups such that no two members of the same group are enemies. You’d like to know if this is possible for your party.
Your friend Euler gives you a graph representing enmity-relationships among the invitees: Each invitee is mapped to a vertex, and an edge \((u, v)\) means invitee \(u\) and invitee \(v\) are enemies.
SeparableEnemySolver class constructor either initializes a
Graph from an input
file, or uses a
Graph instance passed in.
Implement the function
isSeparable() in the
SeparableEnemySolver class, which
true if the invitees represented by
g are separable, and
otherwise. Your solution should run in \(O(V+E)\) time where \(V\) is the number of
people, and \(E\) is the number of enemy relationships.
As usual, submit your solution to Gradescope.
(Optional) Extra Challenge
You are now allowed to separate the party-goers into three groups, again with the restriction that no two members of the same group are enemies. Write another solver that will see if this is possible for a given party.