How to create distinct set from other sets?

Question

While solving the problems on Techgig.com, I got struck with one one of the problem. The problem is like this:

A company organizes two trips for their employees in a year. They want to know whether all the employees can be sent on the trip or not. The condition is like, no employee can go on both the trips. Also to determine which employee can go together the constraint is that the employees who have worked together in past won't be in the same group. Examples of the problems:

Suppose the work history is given as follows: {(1,2),(2,3),(3,4)}; then it is possible to accommodate all the four employees in two trips (one trip consisting of employees 1& 3 and other having employees 2 & 4). Neither of the two employees in the same trip have worked together in past. Suppose the work history is given as {(1,2),(1,3),(2,3)} then there is no way possible to have two trips satisfying the company rule and accommodating all the employees.

Can anyone tell me how to proceed on this problem?

I am using this code for DFS and coloring the vertices.

static boolean DFS(int rootNode) {
        Stack<Integer> s = new Stack<Integer>();
        s.push(rootNode);
        state[rootNode] = true;
        color[rootNode] = 1;
        while (!s.isEmpty()) {
            int u = s.peek();
            for (int child = 0; child < numofemployees; child++) {
                if (adjmatrix[u][child] == 1) {
                    if (!state[child]) {
                        state[child] = true;
                        s.push(child);
                        color[child] = color[u] == 1 ? 2 : 1;
                        break;
                    } else {
                        s.pop();
                        if (color[u] == color[child])
                            return false;
                    }    

                }
            }
        }
        return true;
    }

Answer 1

I even used a recursive solution but this one is also passing the same number of cases. Am I leaving any special case handling ?

Below is the recursive solution of the problem:

static void dfs(int v, int curr) {
        state[v] = true;
        color[v] = curr;

        for (int i = 0; i < numofemployees; i++) {
            if (adjmatrix[v][i] == 1) {
                if (color[i] == curr) {
                    bipartite = false;
                    return;
                }

                if (!state[i])
                    dfs(i, curr == 1 ? 2 : 1);
            }
        }
    }

I am calling this function from main() as dfs(0,1) where 0 is the starting vertex and 1 is one of the color

Answer 2

This problem is functionally equivalent to testing if an undirected graph is bipartite. A bipartite graph is a graph for which all of the nodes can be distributed among two sets, and within each set, no node is adjacent to another node.

To solve the problem, take the following steps.

1. Using the adjacency pairs, construct an undirected graph. This is pretty straightforward: each number represents a node, and for each pair you are given, form a connection between those nodes.
2. Test the newly generated graph for bipartiteness. This can be achieved in linear time, as described here.
3. If the graph is bipartite and you've generated the two node sets, the answer to the problem is yes, and each node set, along with its nodes (employees), correspond to one of the two trips.

Excerpt on how to test for bipartiteness:

It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in linear time, using depth-first search. The main idea is to assign to each vertex the color that differs from the color of its parent in the depth-first search tree, assigning colors in a preorder traversal of the depth-first-search tree. This will necessarily provide a two-coloring of the spanning tree consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-tree edges. In a depth-first search tree, one of the two endpoints of every non-tree edge is an ancestor of the other endpoint, and when the depth first search discovers an edge of this type it should check that these two vertices have different colors. If they do not, then the path in the tree from ancestor to descendant, together with the miscolored edge, form an odd cycle, which is returned from the algorithm together with the result that the graph is not bipartite. However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite.