leetcode207：课程表

题目链接

leetcode

题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

C++ 代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

/*
    深度优先搜索 DFS
    
    遍历图结构，就可以判断环。
    使用布尔数组，若遍历过程中发现下一个即将遍历的节点已被标记为 true，则说明遇到了环。
*/
class Solution_0 {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 邻接矩阵存储图结构
        vector<vector<int>> graph(numCourses);
        for (const auto& edge : prerequisites) {
            int from = edge[1], to = edge[0];
            graph[from].push_back(to);
        }
        path.resize(numCourses, false);
        visited.resize(numCourses, false);
        // 遍历图中所有节点
        for (int i = 0; i < numCourses; i ++) {
            dfs(graph, i);
        }

        // 若不存在环，则可以完成所有课程
        return !hasCycle;
    }

    void dfs(vector<vector<int>>& graph, int s) {
        if (path[s]) hasCycle = true;       // 存在环
        if (visited[s] || hasCycle) return; // 已找到环，结束

        // 先序遍历位置
        visited[s] = true;
        path[s] = true;
        for (int t : graph[s]) {
            dfs(graph, t);
        }
        // 后序遍历位置
        path[s] = false;
    }

private:
    vector<bool> path;     // 记录当前路径上的节点
    vector<bool> visited;  // 记录已经遍历的节点，防止走回头路
    bool hasCycle = false; // 记录图中是否有环
};

/*
    广度优先搜索 BFS

    遍历图结构，就可以判断环。
    使用布尔数组，若遍历过程中发现下一个即将遍历的节点已被标记为 true，则说明遇到了环。
*/
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses); // 邻接矩阵存储图结构
        vector<int> inDegree(numCourses);      // 每个点的入度
        for (int i = 0; i < prerequisites.size(); i ++) {
            int to = prerequisites[i][0], from = prerequisites[i][1];
            graph[from].push_back(to);
            inDegree[to] ++;            
        }

        // 初始化队列中的节点
        queue<int> q;
        for (int i = 0; i < numCourses; i ++) {
            // 若节点 i 没有入度，则可以作为拓扑排序的起点，加入队列
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }

        int count = 0; // 记录遍历节点的个数
        // 执行 BFS 循环
        while (!q.empty()) {
            // 删除边时，弹出节点 cur 并将指向节点的入度 -1
            int cur = q.front(); q.pop();
            count ++;
            for (int next : graph[cur]) {
                inDegree[next] --;
                if (inDegree[next] == 0) {
                    // 若入度变为 0，则说明 next 依赖的节点都已被遍历
                    q.push(next);
                }
            }
        }

        // 若所有节点都被遍历过，则说明不存在环
        return count == numCourses;
    }
};

int main() {
    // 示例输入
    Solution solution;
    int numCourses = 2;
    vector<vector<int>> prerequisites = {{1,0},{0,1}};

    // 判断是否可能完成所有课程的学习
    bool result = solution.canFinish(numCourses, prerequisites);
    // 打印结果
    cout << "Can Finish All Courses: " << (result ? "true" : "false") << endl;

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
	基本思路：
        图的表示：
            使用邻接表表示图，其中每个课程指向其后续课程。
        深度优先搜索（DFS）：
            使用 DFS 遍历图，检测是否存在环。
            使用三种状态标记节点：
                0：未访问
                1：正在访问（当前路径中）
                2：已访问（完成访问）
        环检测：
            如果在 DFS 中遇到一个正在访问的节点（状态为 1），则说明存在环，返回 false。
            如果所有节点都能完成访问，则说明不存在环，返回 true。

    时间复杂度：O(V+E)
        其中 V 是课程总数，E 是先修课程对的数量。
        每个课程和每条边最多被访问一次，因此时间复杂度为 O(V+E)。
    空间复杂度：O(V+E)
        邻接表的空间复杂度为 O(V+E)。
        访问状态数组的空间复杂度为 O(V)。
        因此，总空间复杂度为 O(V+E)。
*/
func canFinish(numCourses int, prerequisites [][]int) bool {
    // 构建邻接表表示图
	graph := make([][]int, numCourses)
	for _, pair := range prerequisites {
        to, from := pair[0], pair[1]
		graph[from] = append(graph[from], to)
	}

	// 访问状态：0=未访问，1=正在访问，2=已访问
	visited := make([]int, numCourses)

	// 深度优先搜索，检测环
	var dfs func(course int) bool
	dfs = func(course int) bool {
		if visited[course] == 1 {
			// 如果当前课程正在访问中，说明存在环
			return false
		}
		if visited[course] == 2 {
			// 如果当前课程已访问过，跳过
			return true
		}

		// 标记当前课程为正在访问
		visited[course] = 1

		// 遍历当前课程的所有后续课程
		for _, nextCourse := range graph[course] {
			if !dfs(nextCourse) {
				return false
			}
		}

		// 标记当前课程为已访问
		visited[course] = 2
		return true
	}

	// 遍历所有课程
	for i := 0; i < numCourses; i++ {
		if !dfs(i) {
			return false
		}
	}
	return true
}

/*
	基本思路：
        图的构建：
            使用邻接表表示图，graph[i] 存储课程 i 的所有后续课程。
            使用 inDegree 数组记录每个课程的入度（即指向该课程的边的数量）。
        BFS 遍历：
            使用队列存储所有入度为0的课程（即没有先修课程的课程）。
            每次从队列中取出一个课程，将其后续课程的入度减1。
            如果某个后续课程的入度变为0，则将其加入队列。
        检测环：
            如果所有课程都被访问过（courseCount == numCourses），则不存在环，返回 true。
            如果队列为空但仍有课程未访问，则存在环，返回 false。

    时间复杂度：O(V+E)
        其中 V 是课程总数，E 是先修课程对的数量。
        每个课程和每条边最多被访问一次，因此时间复杂度为 O(V+E)。
    空间复杂度：O(V+E)
        邻接表的空间复杂度为 O(V+E)。
        入度数组和队列的空间复杂度为 O(V)。
        因此，总空间复杂度为 O(V+E)。
*/
func canFinish_2(numCourses int, prerequisites [][]int) bool {
	// 构建邻接表表示图
	graph := make([][]int, numCourses)
    // 存储每个课程的入度
	inDegree := make([]int, numCourses)

	// 初始化图和入度数组
	for _, pair := range prerequisites {
        to, from := pair[0], pair[1]
		graph[from] = append(graph[from], to)
		inDegree[to]++
	}

	// 使用队列存储入度为 0 的课程
	queue := []int{}
	for i, degree := range inDegree {
		if degree == 0 {
			queue = append(queue, i)
		}
	}

	// BFS 遍历
	courseCount := 0
	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]
		courseCount ++

		// 遍历当前课程的所有后续课程
		for _, nextCourse := range graph[current] {
			inDegree[nextCourse] --
			if inDegree[nextCourse] == 0 {
				queue = append(queue, nextCourse)
			}
		}
	}

	// 如果所有课程都被访问过，则不存在环
	return courseCount == numCourses
}

func main() {
	// 测试用例
	testCases := []struct {
		numCourses    int
		prerequisites [][]int
		expected      bool
	}{
		{
			numCourses:    2,
			prerequisites: [][]int{{1,0}},
			expected:      true,
		},
		{
			numCourses:    2,
			prerequisites: [][]int{{1,0}, {0,1}},
			expected:      false,
		},
	}

	for i, tc := range testCases {
        fmt.Printf("Test Case %d, Input: numCourses = %d, prerequisites = %v\n", i+1, tc.numCourses, tc.prerequisites)
		result := canFinish(tc.numCourses, tc.prerequisites)

        if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %d)\n", i+1, result, tc.expected)		
        }
	}
}