Graphs - Bipartite

An undirected graph is said to be bipartite if its nodes can be partitioned into two disjoint sets \(L, R\) such that there are no edges between any two nodes in the same set.

Example:

Consider the following graph.


graphs-prob-friendless/bipartite.png

This is a bipartite graph because if we set \(L = \{0, 2, 4\}\) and \(R=\{1,3,5\}\) then there are no edges between any two nodes in \(L\) nor \(R\). To better see this, we can draw the graph again by putting the nodes in \(L\) on the left and the nodes in \(R\) on the right.


graphs-prob-friendless/bipartite2.png

Checking whether an undirected graph is bipartite graph should be an easy task by adapting the BFS code. We encourage you to try to write you own algorithm to do so.

It can also be computed using the distance array. Just compute the distance labels on each connected component, starting at any node on the left for each of them. Then loop over the edges and check whether every edge links a node with even distance to a node with odd distance. The graph will be bipartite if and only if this holds.

The reason why this works is that paths starting on \(L\) on a bipartite graph must alternate between \(L\) and \(R\). Thus, as there are no edges within the sets, the distances must also alternate between even and odd from one side to the other. The first node will be even (distance 0) on the left then its neighbors will be odd (distance 1) on the right, then the neighbors of the neighbors will be even (distance 2) on the left and so on.

The following animation illustrates this.

graphs-prob-friendless/anim.gif

One can observe that a graph is bipartite if and only if it does not contain a cycle of odd length. This is because we saw that any path must alternate between even and odd distances. Thus, since a cycle starts and ends at the same node, it would mean that some node in the cycle is both labeled as even and odd which is impossible.

This is an important result that we will use later. It also means that now we have a simple way to check whether a graph contains cycles of odd length.


Friendless - BAC Round 3 2017

Bob, Alice and Craig are going on a school field trip. There are a total of \(n\) students that will travel on two buses. Both buses have capacity \(n\) and the kids can be assigned to the buses in any way the teachers want. The teachers have noticed that the kids are troublesome when they travel with their friends.

The teachers know that gossip ends friendships. Obviously two people will not gossip about a third one if the three of them are on the same bus. Since everyone loves gossip, the kids in one bus will always gossip about everyone that is on the other bus.

Therefore the teachers would like to split the kids between the buses so that after the trip, no two kids are friends because of gossip.

It is very evil but such a relief for them. Could you help them know whether their evil plan is achievable?

Input

The first line of the input contains two integers \(n\) and \(m\) giving the number of kids in the class and the number of friendships (pairs of kids that are friends with each other).

Then follow \(m\) lines each with two integers \(x\) and \(y\) meaning that kid \(x\) is friends with kid \(y\). For simplicity, the kids are numbered from \(0\) to \(n - 1\). Assume that friendships are symmetric, meaning that is \(x\) is friends with \(y\) then \(y\) is friends with \(x\).

Constraints

  • \(1 \leq r, c \leq 1000\)
  • \(1 \leq n \leq 10000\)
  • \(0 \leq m \leq min(50000, n (n - 1) / 2)\)
  • \(0 \leq x, y < n\)
  • \(x \neq y\)

Output

A single line with 'yes' if the teachers can split the kids so that all friendships are destroyed by gossip or 'no' otherwise.

Sample Test Cases

Sample input 1

Sample output 1

Sample input 2

Sample output 2


Max file size: 1.0MB
Allowed extensions: .java, .cpp, .py

Information

Author(s) François Aubry
Deadline No deadline
Submission limit No limitation

Sign in