algo-aha

图着色就是简单的dfs

dfs是否有环

• https://leetcode.com/problems/course-schedule/

直接用visited[]数组

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    // 每个节点用dfs查环
    vector<vector<int>> graph(numCourses);
    for (const auto &edge : prerequisites) {
        graph[edge[1]].push_back(edge[0]);
    }
    vector<bool> visited(numCourses);
    for (int i = 0; i < numCourses; i++) {
        if (hasCycle(i, graph, visited)) return false;
    }
    return true;
}

bool hasCycle(int u, const vector<vector<int>> &graph, vector<bool> &visited) {
    if (visited[u]) return true;
    visited[u] = true;
    for (int v : graph[u]) {
        if (hasCycle(v, graph, visited)) return true;
    }
    visited[u] = false;
    return false;
}

或者，用color[]数组表示各节点颜色（状态）：{ UNVISITED, VISITING, VISITED }。如果已着色（!=UNVISITED），在dfs开头就能判断是否有环（==VISITING）。访问邻接点前把当前节点设为VISITING，访问后把当前节点设为VISITED。

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    // 每个节点用dfs查环，即dfs时遇到标记为VISITING的节点
    // 0: UNVISITED, 1: VISITING, 2: VISITED
    vector<vector<int>> graph(numCourses);
    for (const auto &edge : prerequisites) {
        graph[edge[1]].push_back(edge[0]);
    }
    vector<int> color(numCourses, 0);
    for (int i = 0; i < numCourses; i++) {
        if (hasCycle(i, graph, color)) return false;
    }
    return true;
}

bool hasCycle(int u, const vector<vector<int>> &graph, vector<int> &color) {
    if (color[u] != 0) return color[u] == 1;
    color[u] = 1;
    for (int v : graph[u]) {
        if (hasCycle(v, graph, color)) return true;
    }
    color[u] = 2;
    return false;
}

是否二分图

dfs或bfs遍历着色。当前节点若已着色，看它是不是希望的颜色就能判断是否二分。若未着色，着色后再看邻接点。

• https://leetcode.com/problems/possible-bipartition/
• https://leetcode.com/problems/is-graph-bipartite/

bool isBipartite(vector<vector<int>>& graph) {
    const int N = graph.size();
    vector<int> color(N, -1);
    for (int i = 0; i < N; i++) {
        if (color[i] == -1 && !canColor(i, 0, graph, color)) return false;
    }
    return true;
}

bool canColor(int node, int c, vector<vector<int>> &graph, vector<int> &color) {
    if (color[node] != -1) return color[node] == c;
    color[node] = c;
    for (int neighbor : graph[node]) {
        if (!canColor(neighbor, 1 - c, graph, color)) return false;
    }
    return true;
}

m着色：能否用最多m种颜色着色

• http://www.geeksforgeeks.org/backttracking-set-5-m-coloring-problem/

// 回溯法：对[k,..]顶点完成m着色，0<=k<V
bool graphColoring(int k, int m, int color[], bool G[V][V]) {
    if (k == V) return true;
    for (int c = 0; c < m; c++) {
        if (canColor(k, c, color, G)) {
            color[k] = c;
            if (graphColoring(k + 1, m, color, G)) return true;
            color[k] = -1;
        }
    }
    return false;
}

// 能否对顶点k着c色，要看k的邻接点有没有已着c色的
bool canColor(int k, int c, int color[], bool G[V][V]) {
    for (int i = 0; i < V; i++) {
        if (G[k][i] && color[i] == c) { // 看k的邻居节点i
            return false;
        }
    }
    return true;  
}