Uva 1613 染色问题 之 通过dfs进行结点的染色

一、题意

给出一个n个点m条边的连通图，每个点的度数不超过k（k为一个奇数），要求给每个点进行1...k的染色，使得相邻点颜色不同。

二、解析

首先按照题目的意思求出k，并且题目已经告诉我们k染色一定有解，因此接下来就是放心的dfs染色即可。
需要维护一个col[maxn]数组，0表示没有染色。这个col数组除了存放每个点的颜色，还充当了vis的角色。dfs的出口就是检查是否和周围已经染色的点重色了，没有则进行递归染色即可。

三、代码

#include <iostream>
#include <vector>
using namespace std;
const int maxn = 10000 + 5;
int n, m, k, col[maxn];
vector<int> G[maxn];

bool dfs(int u, int c) {
    col[u] = c;
    for(int v : G[u]) if(col[v] == c) {
        col[u] = 0;
        return 0;
    }
    // 由于可以保证一定有解，所以后面直接找解即可；否则还应该进行return 0的判断。
    for(int v : G[u]) if(!col[v]) {
        for(int i = 1; i <= k; i ++) if(dfs(v, i)) break;
    }
    return 1;
}

int main() {
    bool first = 1;
    while(cin >> n >> m) {
        k = 0;
        fill(col, col + n + 1, 0);
        for(int i = 1; i <= n; i ++) G[i].clear();

        while(m --) {
            int u, v;
            cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        for(int i = 1; i <= n; i ++) k = max(k, (int)G[i].size());
        if(k % 2 == 0) k ++;
        dfs(1, 1);

        if(first) first = 0;
        else cout << endl;
        cout << k << endl;
        for(int i = 1; i <= n; i ++) cout << col[i] << endl;
    }
}

四、归纳

• 染色问题 通过dfs解决，模板大致为：

  bool dfs(int u, int c) {
    col[u] = c;
    // 根据 [已染色的结点] 进行重色判断， 重色则失败
    for(int v : G[u]) if(col[v] == c) {
        col[u] = 0;
        return 0;
    }
  
    // 尝试对 [没染色的结点] 进行染色，同时也要进行是否成功的判断
    bool res = 1;
    for(int v : G[u]) if(!col[v]) {
        bool ok = 0;
        for(int i = 1; !ok && i <= k; i ++) if(dfs(v, i)) ok = 1;
        if(!ok) {   // 若某个点所有染色都染不了，则该次染色失败
            res = 0;
            break;
        }
    }
    return res;
  }