## 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.