目录

力扣 210. 课程表 II（DFS）

OpenJ_Bailian - 4084 拓扑排序（BFS）

有向无环图的拓扑排序是指给所有节点排序，使得所有的有向边都是从序号小的节点指向序号大的。

深度优先搜索和广度优先搜索都可以用于产生拓扑排序。

力扣 210. 课程表 II（DFS）

现在你总共有 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] 。
说明:

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

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
所有[ai, bi] 互不相同

      class Solution2 {
      public:
     	bool canFinish(vector<vector<int>>& diag, int loc) {
     		if (visitt[loc] == 1)return false;
     		if (flag[loc] == 1)return true;
      		visitt[loc] = 1, flag[loc] = 1;
     		for (int i = 0; i < diag[loc].size(); i++)
      		{
     			if (!canFinish(diag, diag[loc][i]))return false;
      		}
      		visitt[loc] = 0;
     		return true;
      	}
     	bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
      		vector<int>tmp;
      		vector<vector<int>>diag;
     		for (int i = 0; i < numCourses; i++)
      		{
      			diag.insert(diag.end(), tmp);
      			visitt[i] = 0, flag[i] = 0;
      		}
     		for (int i = 0; i < prerequisites.size(); i++)
      		{
      			diag[prerequisites[i][0]].push_back(prerequisites[i][1]);
      		}
     		for (int i = 0; i < numCourses; i++)
      		{
     			if (flag[i])continue;
      			cout << i;
     			if (!canFinish(diag, i))return false;
      		}
     		return true;
      	}
      private:
      	map<int, int>visitt;//单次访问标记
      	map<int, int>flag;//所有访问标记
      };
      class Solution {
      public:
     	void findOrder(vector<vector<int>>& diag, int loc, vector<int>& ans)
      	{
     		if (outNum[loc] || flag[loc])return;
      		ans.push_back(loc);
      		flag[loc]++;
     		for (int i = 0; i < diag[loc].size(); i++)
      		{
      			outNum[diag[loc][i]]--;
     			findOrder(diag, diag[loc][i], ans);
      		}
      	}
     	vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
      		vector<int>tmp;
     		if (!Solution2().canFinish(numCourses, prerequisites))return tmp;
      		vector<vector<int>>diag;
     		for (int i = 0; i < numCourses; i++)
      		{
      			diag.insert(diag.end(), tmp);
      			visitt[i] = 0, outNum[i] = 0, flag[i] = 0;
      		}
     		for (int i = 0; i < prerequisites.size(); i++)
      		{
      			diag[prerequisites[i][1]].push_back(prerequisites[i][0]);
      			outNum[prerequisites[i][0]]++;
      		}
      		vector<int>ans;
      		flag.clear();
     		for (int i = 0; i < numCourses; i++)
      		{
     			findOrder(diag, i, ans);
      		}
     		return ans;
      	}
      private:
      	map<int, int>visitt;//单次访问标记
      	map<int, int>flag;//所有访问标记
      	map<int, int>inNum;//入度
      	map<int, int>outNum;//出度
      };
  
 

  
 
 

OpenJ_Bailian - 4084 拓扑排序（BFS）

给出一个图的结构，输出其拓扑排序序列，要求在同等条件下，编号小的顶点在前。

Input

若干行整数，第一行有2个数，分别为顶点数v和弧数a，接下来有a行，每一行有2个数，分别是该条弧所关联的两个顶点编号。
v<=100, a<=500

Output

若干个空格隔开的顶点构成的序列(用小写字母)。

Sample

6 8
1 2
1 3
1 4
3 2
3 5
4 5
6 4
6 5

v1 v3 v2 v6 v4 v5

注意这题输出的顺序，要输出所有拓扑排序的最小字典序的那个。

      #include <iostream>
      #include <string>
      #include <vector>
      #include <string.h>
      #include <map>
      #include <queue>
      using namespace std;
      //输入有向边集{{1，2}{1，3}{2，3}}，输出邻接表{1:{2,3},2:{3}}
      map<int, vector<int>> edgeToAdjaList(const vector<vector<int>>& v)
      {
      	map<int, vector<int>> ans;
     	for (auto &vi : v) {
      		ans[vi[0]].push_back(vi[1]);
      	}
     	return ans;
      }
      //拓扑排序 BFS版
      //输入n=3，v={{0,1}{0,2}{1,2}}, 输出{0,1,2}，有环则输出为空
      vector<int> TopoSort(int n, const vector<vector<int>>&v)
      {
      	priority_queue<int, vector<int>, greater<int>> q;
      	map<int, int>m;
     	for (auto vi : v)m[vi[1]]++;
     	for (int i = 0; i < n; i++)if(m[i]==0)q.push(i);
      	vector<int>ans;
     	auto mv = edgeToAdjaList(v);
     	while (!q.empty()) {
     		int k = q.top();
      		q.pop();
      		ans.push_back(k);
     		for (auto i : mv[k]) {
      			m[i]--;
     			if (m[i] == 0)q.push(i);
      		}
      	}
     	return ans.size() == n ? ans : vector<int>{};
      }
      int main()
      {
     	//freopen("D:/in.txt", "r",stdin);
     	int v, a, x, y;
      	cin >> v >> a;
      	vector<vector<int>> p;
     	while (a--) {
      		cin >> x >> y;
      		p.push_back(vector<int>{x-1, y-1});
      	}
     	auto ans = TopoSort(v, p);
     	for (int i = 0; i < ans.size(); i++)cout << "v" << ans[i]+1 << " ";
      	cout << endl;
     	return 0;
      }
  
 

  
 
 

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/126678850