算法期中练习——1004. 拓扑序

Description:

在图论中，拓扑序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列. 且该序列必须满足下面两个条件：

每个顶点出现且只出现一次.

若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面.
对于一个含有n个节点的有向无环图（节点编号0到n-1），输出它的一个拓扑序.
图的节点数和边数均不多于100000，保证输入的图是一个无环图.

Example:

例1：
n = 3，edges = {(0, 1), (0, 2)}，函数应返回{0, 1, 2}或者{0, 2, 1}.

例2：
n = 4，edges = {(0, 1), (0, 2), (1, 2), (3, 0)}，函数应返回{3, 0, 1, 2}.

请为下面的Solution类实现解决上述问题的topologicalSort函数，函数参数中n为图的节点数，edges是边集，edges[i]表示第i条边从edges[i].first指向edges[i].second. 函数返回值为有向图的一个拓扑序. 有向图有多个拓扑序时，输出任意一个即可.

class Solution {
public:
       vector<int> topologicalSort(int n, vector<pair<int, int>>& edges) {
          
    }
};

Solution #1

具体算法可以看代码注释，很详细。
这里我给出例2的手工求解过程：

初始化inDegree和reach：
inDegree[1] = 1, reach[0] -> 1
inDegree[2] = 1, reach[0] -> 2
inDegree[2] = 2, reach[1] -> 2
inDegree[0] = 1, reach[3] -> 0
inDegree[3] = 0

因为3的入度为0，此时将3放进队列inDegreeZero；
进入循环，present=3，reach[present]有一个数，为0
0的入度为1，故减一后temp=0，将0加入队列inDegreeZero，弹掉队列头3，将3加入结果数组res中；

继续循环，present=0，reach[present]有两个数，为1，2；线判断1，1的入度为1，故减一后temp=0，将1加入队列inDegreeZero中；再判断2，2的入度为2，故减一后temp=1，退出for循环，弹掉队列头0，将0加入结果数组res中；

继续循环，present=1，reach[present]有一个数，为2，2的入度为1，故减一后temp=0，将2加入队列inDegreeZero，弹掉队列头1，将1加入结果数组res中；

继续循环，present=2，reach[present]没有数，不进入for循环，弹出队列头2，将2加入结果数组res中；

整个循环结束，res中的值为3, 0, 1, 2.

代码如下：

class Solution {
public:
	vector<int> topologicalSort(int n, vector<pair<int, int>>& edges) {
		vector<int> res;
		int *inDegree = new int[n];// 记录每个点的入度
		for (int i = 0; i < n; i++) {
			inDegree[i] = 0;
		}

		queue<int> inDegreeZero;// 存储入度为0的点
		vector<vector<int>> reach(n);// 存储邻接表
		for (int i = 0; i < edges.size(); i++) {
			inDegree[edges[i].second]++;// 记录每个点的入度
			reach[edges[i].first].push_back(edges[i].second);// 把每条边存储成邻接表
		}
		for (int i = 0; i < n; i++) {
			if (inDegree[i] == 0) 
				inDegreeZero.push(i);// 存储入度为0的点
		}

		while (res.size() < n) {
			int present = inDegreeZero.front();// 每次取队列的第一个元素输出
			for (int i = 0; i < reach[present].size(); i++) {// 从入度为0的点开始，遍历该点连接的边
				// 判断更新完连接点的入度是否为0，是则加入队列
				int temp = (--inDegree[reach[present][i]]);
				if (temp == 0) {
					inDegreeZero.push(reach[present][i]);
				}
			}
			inDegreeZero.pop();
			res.push_back(present);
		}
		return res;
	}
};

Solution #2

和Solution #1差不多，只不过边的存储颠倒过来，例如(0, 1)这条边在Solution #1存储为reach[0]->1，而在Solution #2存储为V[1]->0，这里我给出算法的手工求解过程：
初始化V：
u=0, v=1, v[1]->0
u=0, v=2, v[2]->0
u=1, v=2, v[2]->1
u=3, v=0, v[0]->3

初始化vis:
vis[0]=vis[1]=vis[2]=vis[3]=false

进入for循环，对每一个还未访问过的点进行dfs：

首先dfs(0)，由于v[0]->3，且3还未访问过，故dfs(3)，
又由于没有v[3]，故将3加入到结果数组ans中，

此时dfs函数中退出for循环，再把0加入到结果数组ans中，

回到topologicalSort函数，接下来进行dfs(1)，
由于v[1]->0，而0已被访问过，所以直接将1加入到结果数组ans中，

回到topologicalSort函数，接下来进行dfs(2)，
由于有v[2]->0和v[2]->1，而0和1都已被访问过，故将2加入到结果数组ans中，

回到topologicalSort函数，由于3已被访问过，故求解过程结束，返回结果数组ans=[3, 0, 1, 2].

代码如下：

class Solution {
private:
	vector<vector<int> > V;
	vector<int> ans;
	vector<bool> vis;
	void dfs(int u) {
		int v, i;
		vis[u] = true;
		for (i = 0; i < V[u].size(); i++) {
			v = V[u][i];
			if (!vis[v]) dfs(v);
		}
		ans.push_back(u);
	}
public:
	vector<int> topologicalSort(int n, vector<pair<int, int>>& edges) {
		int u, v, i;
		V.resize(n);
		vis.resize(n);
		for (i = 0; i < edges.size(); i++) {
			u = edges[i].first;
			v = edges[i].second;
			V[v].push_back(u);
		}
		for (i = 0; i < n; i++) vis[i] = false;
		for (i = 0; i < n; i++) if(!vis[i]) dfs(i);
		return ans;
	}
};