题目链接：https://www.dotcpp.com/oj/problem1707.html
常规问题常规做法，用bfs拓扑思想即可。
但这个题有一个坑点是用队列反而不行了，要用到dfs拓扑思想的队列。
也就是说这个题是dfs+bfs双拓扑思想。
当然，我发现大多数算法思想是依据bfs拓扑思想的，所以说算法实现起来不算太难。
今晚我会根据情况总结一下拓扑排序的简单算法，当然，
拓扑排序的重要应用—关键路径算法我还没完全掌握，所以会根据情况做一下拓扑排序的小结；
回到本题，这个题还要一个小技巧，
就是存图的时候依然是用邻接表存的，虽然题目貌似是要求用邻接矩阵存图。
但是用邻接表存图也是可以的，只要在循环中定义一个临时变量，每次输入这个临时变量并且判断，
如果满足条件就按照拓扑排序的算法进行入度操作；
然后进行常规的拓扑排序算法实现就可以了。
Talk is cheap. Show me the code.
队列代码（仅供参考，当然正规是这样写的，这个题有坑点不会过）
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int num=30010;
4 queue<int>q;
5 int n;
6 vector<int>edge[num];
7 vector<int>topo;
8 int in[num];
9 int main()
10 {
11 std::ios::sync_with_stdio(false);
12 cin>>n;
13 for(register int i=0;i<n;i++)
14 {
15 for(register int j=0;j<n;j++)
16 {
17 int temp;
18 cin>>temp;
19 if(temp)
20 {
21 edge[i].push_back(j);
22 in[j]++;
23 }
24 }
25 }
26 for(register int i=0;i<n;i++)
27 {
28 if(!in[i])
29 q.push(i);
30 }
31 while(!q.empty())
32 {
33 //int x=q.top();
34 int x=q.front();
35 q.pop();
36 topo.push_back(x);
37 for(register int j=0;j<edge[x].size();j++)
38 {
39 int y=edge[x][j];
40 in[y]--;
41 if(!in[y])
42 q.push(y);
43 }
44 }
45 for(register int i=0;i<topo.size();i++)
46 cout<<topo[i]<<" ";
47 return 0;
48 }AC代码
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int num=30010;
4 stack<int>q;//坑点是栈
5 int n;
6 vector<int>edge[num];//邻接表
7 vector<int>topo;//拓扑序列
8 int in[num];//入度数组
9 int main()
10 {
11 std::ios::sync_with_stdio(false);
12 cin>>n;
13 for(register int i=0;i<n;i++)
14 {
15 for(register int j=0;j<n;j++)
16 {
17 int temp;
18 cin>>temp;//写入临时变量
19 if(temp)//非0
20 {
21 edge[i].push_back(j);//存图
22 in[j]++;//入度
23 }
24 }
25 }
26 for(register int i=0;i<n;i++)
27 {
28 if(!in[i])
29 q.push(i);//将度为0的节点入队（栈）
30 }
31 while(!q.empty())
32 {
33 int x=q.top();//队（栈）首元素
34 q.pop();
35 topo.push_back(x);//读入拓扑序列
36 for(register int j=0;j<edge[x].size();j++)//检查邻居
37 {
38 int y=edge[x][j];
39 in[y]--;///邻居的度减一
40 if(!in[y])//度为0入队（栈）
41 q.push(y);
42 }
43 }
44 for(register int i=0;i<topo.size();i++)
45 cout<<topo[i]<<" ";
46 return 0;
47 }
正文完