求图的色数

Author： Colin
发布时间：May 1, 2020
2163 views
No comments
2028 words
Categories：编程记录技术杂烩

**必读声明**

本博客的代码本着自由之精神而分享。如果读者在修读某门课程，而课程要求不能参阅资料，不能抄袭、套用他人代码，或者要求签署honor code等等，请立即按照要求进行操作，包括不限于立即关闭本页面停止阅读，或者在要求的位置填写参考资料的信息。本人在此已经尽到告知之义务，对所有读者的行为不负有任何责任。

# 原问题

给定n门课程，每门课占用一个学期里1~m个时段中的一些时段。比如第一门课占用1、3、5，第二门课占用2、4、6。显然同一个学生同一学期不能上两门时间冲突的课程，冲突的课程只能放在不同的学期去上。现在给出这些课程信息，求一个学生要上完这些课程至少需要的学期的数量。
原样例：
```
5 5
2 1 3
2 2 5
1 3
0
3 1 2 4
```
含义：
n=5, m=5（一共m个时段）；
第一个课程占用2个时段，分别是1、3；
……（直到第n=5个课程）

# 建模

看上去像二分图匹配的拓展情况。但是它连二分图多重匹配都不是，因为有一些边需要在某一次中“捆绑”选择，不能拆开，此路不通。
想当然地会想到贪心，即每次选尽可能多的，从前往后扫描即可。这样可以得98分，在case 25上过不去。贪心的错误来源于选择的方式会受到扫描顺序的影响，比如下面这个答案为3的反例：

```
5 5
2 1 3
3 1 2 4
2 1 5
2 2 4
2 4 5
```

只好再换一种方法。

如果根据每门课的占用时间，生成一个图，方法为：每门课为一个结点；如果两门课的时间冲突了，那就用一条边连接它们。这样，相邻的结点不能在同一学期，并且只要不相邻的结点意味着他们没有发生冲突，于是可以在同一学期。因此只要保证相邻节点的学期序号不同即可。于是问题就转化为了求简单图（无重边、无自环）的色数。

# 算法

首先建立反映冲突情况的简单图G。建立方法可以是一遍读入一边建立。对于某课程i，读入到其占用了时间time，那么令`data[i][time] = 1`。遍历i之前的课程j，若`data[j][time] = 1`，说明j也占用了时间time，课程i、j发生了冲突，那么令`g[i][j] = g[j][i] = 1 `，即在G中添加边(i, j)。

然后就是根据课本上的定理4.6.3，通过建立图G'、G''，利用`G的色数=min(G'的色数, G''的色数)`递归地求色数。

首先找到G中任意不相邻的两点i、j。则：G'为G加上边(i, j)后的图；G''为使G中i、j两点“融合”之后的图。“融合”即把i、j缩为1个点，同时与i、j关联的边都关联到融合点上去。

> 所谓定理4.6.3的原理：G'代表了i、j两点染不同颜色的情况（因为连上了所以不能染相同颜色）；G''代表了i、j染相同颜色的情况（缩成一个点了，等价于染一个颜色）。对任意i、j这个道理总是对的。因此递归的时候只需要找出任意的i、j往下递归即可，其它符合条件的i、j在同一个递归层中不必考虑。

然后对G'、G''又可以继续递归地进行这样的生成两种图的操作。一直到图成为完全图之后，就找不到不相邻的两点了，递归终止。根据完全图的色数为它的结点数，求所有生成的完全图中的最小色数，它就是原图G的色数。

在代码实现上，用一个递归函数dfs模拟上述操作即可。维护一个全局色数最小值，每生成一个完全图就更新一下，最后这个值就是所求答案。

# 代码

```c++
//
//  main.cpp
//  t3
//
//  Created by Colin on 2020/05/01.
//  Copyright © 2020 Colin. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 17;

class Paint
{
public:
    int n, m;
    bool (*graph)[maxn];
    bool deleted_node[maxn];
    int cn2[maxn];
    int min_k = maxn + 1;
    
    Paint(const int _n, const int _m, bool (*_g)[maxn]):
        n(_n), m(_m), graph(_g)
    {
        memset(deleted_node, 0, sizeof(deleted_node));
        for (int i = 0; i <= maxn; i++)
            cn2[i] = i * (i - 1) / 2;
        dfs(graph, deleted_node, n, m);
    }
    
    void dfs(bool (*_graph)[maxn], bool *deleted_node, int remained_n, int remained_e)
    {
        if (remained_e == cn2[remained_n])    // reach Kn!
        {
            min_k = min(min_k, remained_n);
            return;
        }
        bool g1[maxn][maxn] = { 0 };
        bool g2[maxn][maxn] = { 0 };
        bool deled_node_2[maxn] = { 0 };
        int remained_n_1 = remained_n;
        int remained_n_2 = remained_n;
        int remained_e_1 = remained_e;
        int remained_e_2 = remained_e;
        // copy the state
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                g2[i][j] = g1[i][j] = _graph[i][j];
        for (int i = 1; i <= n; i++)
            deled_node_2[i] = deleted_node[i];
        
        // link i, j
        bool need_to_break = 0;
        int ii = 0, jj = 0;
        for (int i = 1; i <= n && !need_to_break; i++)
        {
            if (!deleted_node[i])
            {
                for (int j = 1; j <= n && !need_to_break; j++)
                {
                    if (j != i && !deleted_node[j] && !g1[i][j])
                    {
                        g1[i][j] = g1[j][i] = 1;
                        remained_e_1++;    // local variable
                        need_to_break = 1;
                        ii = i;
                        jj = j;
                    }
                }
            }
        }
        dfs(g1, deleted_node, remained_n_1, remained_e_1);
        
        // combine ii, jj
        deled_node_2[jj] = 1;
        remained_n_2--;
        for (int k = 1; k <= n; k++)
        {
            if (!deled_node_2[k] && g2[jj][k])
            {
                g2[jj][k] = g2[k][jj] = 0;
                if (g2[k][ii])
                    remained_e_2--;
                else
                    g2[k][ii] = g2[ii][k] = 1;
            }
        }
        dfs(g2, deled_node_2, remained_n_2, remained_e_2);
    }// end function dfs
    
};

int main()
{
    bool conflict[maxn][maxn] = { 0 };
    int data[maxn][103] = { 0 };
    int n, m;
    int edge = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> data[i][0];
        for (int j = 1; j <= data[i][0]; j++)
        {
            int time = 0;
            cin >> time;
            data[i][time] = 1;
            // construct conflict graph
            for (int course = 1; course < i; course++)
            {
                if (data[course][time])
                {
                    if (!conflict[course][i])
                    {
                        edge++;
                        conflict[course][i] = conflict[i][course] = 1;
                    }
                }
            }
        }
    }
    Paint paint(n, edge, conflict);
    
    cout << paint.min_k << endl;
    
    return 0;
}
```

Last modification：June 4, 2021