Challenge Lab 9: Graphs

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 means invitee and invitee 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 time where is the number of people, and 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.