Partition an integer array into 2 unconnected parts

Question

Given an int array (each elements value is equal to it's index) of the length n and m connections between the array elements. Partition the array into 2 parts (all elements in a part have to be unconnected with respect to the given m connections).

Output true if such a partition exists, otherwise false.

Here are 3 Examples:

1. Given array: {0, 1, 2, 3}

   Given connections: 0-1, 2-3 (0 connected to 1, 2 connected to 3)

   Output should be: true (the partitions are {0,3}, {1,2})

2. Given array: {0, 1, 2}

   Given connections: 1-2, 0-1, 0-2

   Output should be: false (no 2 partitions contain only unconnected elements)

3. Given array: {0,1}

   Given connections: 0-1

   Output should be: true (the partitions are {0}, {1})

My current approach: Form all possible connections between array elements and store them, remove m incoming connections from my stored ones, check if the remaining connections form 2 partitions of the given array. This solution is too slow (I suspect that building all possible connections takes too much time).

Answer 1

The problem is to test whether a given graph is bipartite, i.e. 2-colorable, which can be done efficiently by using depth-first search. Start at an arbitrary node, assigning it any of two colors. For each edge that is iterated, give the target node the color different from the one of its parent. If this is not possible, terminate the search as the input is not bipartite. Otherwise, you have generated a 2-coloring of the graph which indicates the two partitions.