Introduction
In this lab, you’ll investigate the ways graphs can model and solve problems.
The Problem
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.
The SeparableEnemySolver class constructor either initializes a Graph from an input
file, or uses a Graph instance passed in.
Your Task
Implement the function isSeparable() in the SeparableEnemySolver class, which
returns true if the invitees represented by g are separable, and false
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.
Submission
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.