THINK FIRST·CODE LATER

← All labs

Two teams: is the graph bipartite?

Problem

Some pairs of players refuse to be in the same team. Can everybody be split into two teams? Write TwoTeams. Read n m and m pairs u v that must be separated. Colour the graph with BFS: the first vertex of each component (lowest number) goes to team 1, and every neighbour of a vertex goes to the opposite team. If two neighbours end up with the same colour, it is impossible.

Print the two teams, or Impossible: … and the reason.

For the input

6 5
0 1
1 2
2 3
3 4
4 5

the program prints

Team 1: [0, 2, 4]
Team 2: [1, 3, 5]
The graph is bipartite

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d15-5-data-1.txt

6 5
0 1
1 2
2 3
3 4
4 5
What your program must print for d15-5-data-1.txt
Team 1: [0, 2, 4]
Team 2: [1, 3, 5]
The graph is bipartite

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d15-5-data-1.txt

Windows PowerShell does not understand <:

Get-Content d15-5-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.