算法分析课程博客分享 4

785. 判断二分图(Is Graph Bipartite?)

给定一个无向图graph，当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。

graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。

示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释:
无向图如下:
0——1
| |
| |
3——2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。

示例 2:
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释:
无向图如下:
0——1
| \ |
| \ |
3——2
我们不能将节点分割成两个独立的子集。

注意:

graph 的长度范围为 [1, 100]。
graph[i] 中的元素的范围为 [0, graph.length - 1]。
graph[i] 不会包含 i 或者有重复的值。
图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。

解题思路:
这是一道比较经典的题目，判断二分图可以使用着色法求解。具体代码如下:

public:
    bool isBipartite(vector<vector<int>>& graph) {
        vector<int> color(graph.size(), 0);
        for (int i = 0; i < graph.size(); ++i) {
            if (color[i] == 0 && !dfs(graph, color, i, 1))
                return false;
        }
        return true;
    }
    
private:    
    /**
     @param v       index of current vertex
     @param c       color of current vertex
     @return        whether it is bipartite
     */
    bool dfs(vector<vector<int>>& graph, vector<int>& color, int v, int c) {
        color[v] = c;
        for (int i = 0; i < graph[v].size(); ++i) {
            if (color[graph[v][i]] == c)
                return false;
            if (color[graph[v][i]] == 0 && !dfs(graph, color, graph[v][i], -c))
                return false;
        }
        return true;
    }

从题目条件出发，我们可以保证: 图中每一条边的两个节点不来自同一集合。因此，我们可以用两种不同的颜色标记每一条边的两个节点，最终，我们可以将所有节点用两种不同的颜色进行标记。若我们无法完成这个任务，则这个图不是一个二分图。从代码角度出发，首先定义一个名为 color 的数组，记录当前节点的颜色，通过 dfs 的方式遍历每一条边，然后将每一条边的两个节点分别标记为 c 和 -c。若扫描到同一条边的两个节点颜色相同，则可以判断这个图不是一个二分图。

207. 课程表(Course Schedule)

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

说明:

输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。

提示:

这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。

解题思路:
这道题目的要求是判断一个有向图能否进行拓扑排序，而不需要输出一个拓扑排序的结果。因此，我们实际上只需要判断这个有向图是否为 DAG。

首先第一种做法为 Kahn 法，具体代码如下:

bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
    vector<vector<int>> graph(numCourses, vector<int>());
    vector<int> indegree(numCourses, 0);
    queue<int> topo;
    for (int i = 0; i < prerequisites.size(); ++i) {
        graph[prerequisites[i].second].push_back(prerequisites[i].first);
        ++indegree[prerequisites[i].first];
    }
    for (int i = 0; i < numCourses; ++i) {
        if (indegree[i] == 0)
            topo.push(i);
    }
    while (!topo.empty()) {
        int v = topo.front();
        topo.pop();
        for (int i = 0; i < graph[v].size(); ++i) {
            if (--indegree[graph[v][i]] == 0)
                topo.push(graph[v][i]);
        }
        --numCourses;
    }
    return numCourses == 0;
}

这种做法的思路为，每次从节点集合中取出一个入度为 0 的点，然后将其从图中删去，若该图可以进行拓扑排序，则最后的节点集合应该为空集。实际操作的时候，我们需要对 prerequisites 数组进行一个预处理，将其转化为边缘列表。而时间复杂度上，由于第一次的扫描，具体复杂度会略大于 O(V+E)。

第二种做法为 dfs 法，时间复杂度为 O(V+E)，具体代码如下:

public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<vector<int>> graph(numCourses, vector<int>());
        vector<int> visited(numCourses, 0);
        for (int i = 0; i < prerequisites.size(); ++i) {
            graph[prerequisites[i].second].push_back(prerequisites[i].first);
        }
        for (int i = 0; i < numCourses; ++i) {
            if (visited[i] == 0 && !dfs(graph, visited, i))
                return false;
        }
        return true;
    }
    
private:    
    bool dfs(vector<vector<int>>& graph, vector<int>& visited, int v) {
        visited[v] = -1;
        for (int i = 0; i < graph[v].size(); ++i) {
            if (visited[graph[v][i]] == -1)
                return false;
            if (visited[graph[v][i]] == 0 && !dfs(graph, visited, graph[v][i]))
                return false;
        }
        visited[v] = 1;
        return true;
    }

这种做法的思路和上一题的着色法类似，区别在于我们需要用到三种颜色，其中 0 表示没有访问过；1 表示已访问过；-1 表示正在访问中。与上一种做法相同，这种做法也需要对 prerequisites 进行预处理，将其转化为边缘列表。

210. 课程表 II(Course Schedule II)

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例 1:
输入: 2, [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2:
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

说明:

输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。

提示:

这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。

解题思路:
考虑到这一周有实验室的工作要处理，选择了一道比较偷懒的题，其实这道题与上道题的逻辑完全一样，只需要加上拓扑排序结果的输出。

Kahn 法:

vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
    vector<vector<int>> graph(numCourses, vector<int>());
    vector<int> indegree(numCourses, 0);
    queue<int> topo;
    vector<int> ans;
    for (int i = 0; i < prerequisites.size(); ++i) {
        graph[prerequisites[i].second].push_back(prerequisites[i].first);
        ++indegree[prerequisites[i].first];
    }
    for (int i = 0; i < numCourses; ++i) {
        if (indegree[i] == 0)
            topo.push(i);
    }
    while (!topo.empty()) {
        int v = topo.front();
        topo.pop();
        for (int i = 0; i < graph[v].size(); ++i) {
            if (--indegree[graph[v][i]] == 0)
                topo.push(graph[v][i]);
        }
        ans.push_back(v);
        --numCourses;
    }
    return (numCourses == 0) ? ans : vector<int>();
}

dfs 法:

public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<vector<int>> graph(numCourses, vector<int>());
        vector<int> visited(numCourses, 0);
        for (int i = 0; i < prerequisites.size(); ++i) {
            graph[prerequisites[i].second].push_back(prerequisites[i].first);
        }
        for (int i = 0; i < numCourses; ++i) {
            if (visited[i] == 0 && !dfs(graph, visited, i))
                return vector<int>();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
    
private:
    vector<int> ans;
    
    bool dfs(vector<vector<int>>& graph, vector<int>& visited, int v) {
        visited[v] = -1;
        for (int i = 0; i < graph[v].size(); ++i) {
            if (visited[graph[v][i]] == -1)
                return false;
            if (visited[graph[v][i]] == 0 && !dfs(graph, visited, graph[v][i]))
                return false;
        }
        visited[v] = 1;
        ans.push_back(v);
        return true;
    }