Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.md
bfs.cpp
dfs.cpp

README.md

Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note: The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

Hints:

  • This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  • Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  • Topological sort could also be done via BFS.

Solution

显然这是一道拓扑排序题。求拓扑排序的算法过程:

  • 求出所有节点的入度in-degree
  • 搜索in-degree,找出入度为0的节点,若没有找到入读为0的节点,则一定存在环,返回false,否则,从节点中删除该节点,并与之相关联的所有有向边。
  • 重复以上,直到所有的节点访问完毕,返回true

首先求出所有的入度(注意题目的图是后面指向前面):

vector<int> degree(n, 0);
for (auto p : request) {
	//g[p.second][p.first] = 1;
	degree[p.first]++;
}

寻找入度等于0的节点, 返回-1表示没有找到:

int findZero(const vector<int> &v) {
	int n = v.size();
	for (int i = 0; i < n; ++i) {
		if (v[i] == 0)
			return i;
	}
	return -1;
}

实现拓扑排序判断:

bool canTopsort(const vector<pair<int, int>> &request, vector<int> &degree) {
	int n = degree.size();
	vector<bool> visited(n, false);
	int sum = 0;
	while (sum < n) { // 还没有访问完
		int cur = findZero(degree);
		if (cur >= 0) { // 访问节点cur
			sum++;
			degree[cur] = -1; // 标记当前节点为已经访问状态
			for (auto p : request) {
				if (p.second == cur)
					degree[p.first]--; // 去掉已访问节点
			}
		} else
			return false;
	}
	return true;
}

以上方法实质就是BFS,也可以使用DFS,从一个节点出发,顺着边往下走,若回到已经访问的节点,说明存在环。

为了标示正在访问的节点、未访问节点和已经访问节点,我们分别使用-1, 0, 1表示。

bool dfs(const vector<pair<int, int>> &request, vector<int> &visited, int i) {
	if (visited[i] == -1) // 回到了出发点,说明存在环
		return false;
	if (visited[i] == 1) // 已经访问过该节点了
		return true;
	visited[i] = -1; // -1 表示正在访问
	for (auto p : request) {
		if (p.second == i) {
			if (!dfs(request, visited, p.first))  // 访问下一个节点
				return false;
		}
	}
	visited[i] = 1; // 标识为已经访问过
	return true;
}

扩展

Course Schedule II: 输出拓扑排序结果

You can’t perform that action at this time.