This problem can be reduced to a bipartite graph problem.
If the vertices of a graph can be divided into two groups, such that
- there exists no edge between any two vertices in the same group
- (for every node, there is an edge that connects it to a vertex of the other group)
We notice that
- the people will be partitioned into two groups
- only people in different groups share some kind of relationship with each other
Knowing that an (undirected) graph is simply a visualization of a (symmetric) relation, and a partitioning of its objects (i.e. persons) into two groups, and all edges connect vertices from different groups, we can see that this in fact qualifies as a bipartite graph, if such a partitioning is indeed possible.
We conclude that we must only determine, if it is a (relaxed) bipartite graph. Relaxed, because in the proper definition, every vertex must have at least one edge, but the problem does not specify whether that is the case. This is why (2) is in parentheses.
Detecting a bipartite graph
This can be done with either a breadth-first-search (BFS) of a depth-first-search (DFS) algorithm.
- We can place the first vertex into group #1. (It does not matter which)
- Having done that, it is clear that all its neighbors must be placed in group #2, since neighbors are those, that have have worked with the first person. Thus, they may not be in the group #1.
- Similarly, we place all the neighbors' neighbors into group #1
- Continuing the same way, we assign the nodes to the two different groups.
However, in case a bipartite graph cannot be formed, we have to stumble across a node when trying to assign it to group X, that was already assigned to a group, but not group X. In that case, it is impossible to form two groups of employees where nobody has worked with each other before.
Upon discovering a neighboring node, we place it in the opposite group of the currently active node, if it has not been assigned one yet.
In case it has already been assigned to the same node, we know it's impossible to form a bipartite graph.
Otherwise, it has already placed into a group conforming rule (1) of a bipartite graph.
Dealing with rule (2)
In case rule (2) is not in effect, i.e. the graph has more than one connected components, DFS/BFS will terminate before having assigned all nodes to a group.
In that case, the algorithm is simply run again on a yet unassigned node, until no such nodes are left.
Getting all solutions
In case rule(2) is not in effect, there exist more than just two solutions. For a graph with
c connected components, (i.e. the DFS/BFS algorithm was run
c times), there are 2
For that, we need to differentiate between the two groups created by each invocation of the BFS/DFS algorithm: g
c,1 and g
c,2 for run
After having run the algorithm
c times, we distribute the
c pairs to two groups, in which the employees are being separated, freely.