题目链接：https://www.dotcpp.com/oj/problem1707.html
常规问题常规做法，用bfs拓扑思想即可。
但这个题有一个坑点是用队列反而不行了，要用到dfs拓扑思想的队列。
也就是说这个题是dfs+bfs双拓扑思想。
当然，我发现大多数算法思想是依据bfs拓扑思想的，所以说算法实现起来不算太难。
今晚我会根据情况总结一下拓扑排序的简单算法，当然，
拓扑排序的重要应用---关键路径算法我还没完全掌握，所以会根据情况做一下拓扑排序的小结；
回到本题，这个题还要一个小技巧，
就是存图的时候依然是用邻接表存的，虽然题目貌似是要求用邻接矩阵存图。
但是用邻接表存图也是可以的，只要在循环中定义一个临时变量，每次输入这个临时变量并且判断，
如果满足条件就按照拓扑排序的算法进行入度操作；
然后进行常规的拓扑排序算法实现就可以了。
队列代码（仅供参考，当然正规是这样写的，这个题有坑点不会过）
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 }