3

在解决 Techgig.com 上的问题时，我对其中一个问题感到震惊。问题是这样的：

某公司每年为其员工组织两次旅行。他们想知道是否可以将所有员工都送去旅行。条件是，没有员工可以同时参加这两次旅行。此外，要确定哪些员工可以一起工作，限制条件是过去一起工作的员工不会在同一个组中。问题示例：

假设工作历史如下：{(1,2),(2,3),(3,4)}; 然后可以在两次旅行中容纳所有四名员工（一次旅行由员工 1 和 3 组成，另一次由员工 2 和 4 组成）。同一次旅行的两名员工过去都没有一起工作过。假设工作历史为 {(1,2),(1,3),(2,3)}，那么不可能有两次满足公司规则并容纳所有员工的旅行。

谁能告诉我如何处理这个问题？

我将此代码用于 DFS 并为顶点着色。

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;
    }
4

2 回答 2

4

这个问题在功能上等同于测试一个无向图是否是二分图。二分图是所有节点都可以分布在两个集合中的图，并且在每个集合中，没有节点与另一个节点相邻。

要解决此问题，请执行以下步骤。

  1. 使用邻接对，构造一个无向图。这很简单：每个数字代表一个节点，对于给定的每一对，在这些节点之间形成一个连接。
  2. 测试新生成的图的二分性。这可以在线性时间内实现，如此处所述。
  3. 如果图是二分图并且您已经生成了两个节点集，那么问题的答案是肯定的，并且每个节点集及其节点（员工）对应于两次行程之一。

关于如何测试二分性的摘录：

可以测试一个图是否是二分图，并使用深度优先搜索在线性时间内返回双色（如果是二分图）或奇数循环（如果不是）。主要思想是在深度优先搜索树中为每个顶点分配与其父节点颜色不同的颜色，在深度优先搜索树的前序遍历中分配颜色。这将必然提供生成树的两种颜色，该生成树由连接顶点到其父节点的边组成，但它可能无法正确着色某些非树边。在深度优先搜索树中，每个非树边的两个端点之一是另一个端点的祖先，当深度优先搜索发现这种类型的边时，它应该检查这两个顶点是否具有不同的颜色。如果他们不这样做，则树中从祖先到后代的路径与颜色错误的边一起形成一个奇循环，该循环与图不是二分的结果一起从算法返回。但是，如果算法在未检测到此类奇数循环的情况下终止，则必须对每条边正确着色，并且算法将着色与图是二分图的结果一起返回。

于 2012-09-01T06:53:18.390 回答
0

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

于 2012-09-02T09:10:55.647 回答