题目链接
题目给出了一个无环有向图，不带权值，以此来表示一个工作流程，比如下面的第一个图，表示的意思是，要完成B任务，前置需要完成A任务和X任务，要完成Y任务，前置是要完成X任务，以此类推，目的是要找出一种合理的完成任务的顺序，来保证所有任务都可以被完成，有些任务是没有前置要求的，比如A，X，这些任务可以直接完成。
思路有两种，bfs和dfs，我是用队列来实现的
首先用邻接矩阵来存储这个图；
bfs的做法是：
1.遍历所有点，找出没有访问过，而且入度为0的点，放入任务队列
2.完成任务队列的队首元素，标记为已完成，该元素指向的点入度减1，直到任务队列清空
重复上述两步直到所有元素都被访问完成，记录下访问顺序就是答案。
dfs的做法是：
1.先把可以直接访问的点放入任务队列
2.访问任务队列的队首元素，标记为完成，该元素指向的点入度减1，如果该元素入度为0而且未被访问，则把次节点加入到任务队列中
重复步骤2直到所有元素都被访问过为止，记录下访问顺序就是答案。
bfs代码如下：
#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; const int maxx=10010; vector<int> A[maxx],ans; queue<int> task; int f[maxx]; bool flag[maxx]; int v,e; int main (){ int x,y; bool xx=false; cin>>v>>e; for(int i=0;i<maxx;i++){ f[i]=0; flag[i]=false; } while(e--){ cin>>x>>y; A[x].push_back(y); f[y]++; } while(1){ xx=false; for(int i=0;i<v;i++) { if(f[i]==0&&flag[i]==false) { xx=true; task.push(i); } } if(xx==false) break; while(task.empty()==0){ x=task.front(); flag[x]=true; ans.push_back(x); for(int k=0;k<A[x].size();k++){ f[A[x][k]]--; } task.pop(); } } for(int i=0;i<ans.size();i++){ cout<<ans[i]<<endl; } return 0; }错点：
1.队首元素指向的节点是A[x][k] 不是k
dfs代码如下：
#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; const int maxx=10010; vector<int> A[maxx],ans; queue<int> task; int f[maxx]; bool flag[maxx]; int v,e; int main (){ int x,y; bool xx=false; cin>>v>>e; for(int i=0;i<maxx;i++){ f[i]=0; flag[i]=false; } while(e--){ cin>>x>>y; A[x].push_back(y); f[y]++; } for(int i=0;i<v;i++) { if(f[i]==0&&flag[i]==false) { task.push(i); flag[i]=true; } } while(1){ xx=false; while(task.empty()==0){ x=task.front(); ans.push_back(x); for(int k=0;k<A[x].size();k++){ f[A[x][k]]--; if(f[A[x][k]]==0&&flag[A[x][k]]==false) { task.push(A[x][k]); flag[A[x][k]]=true; xx=true; } } task.pop(); } if(xx==false) break; } for(int i=0;i<ans.size();i++){ cout<<ans[i]<<endl; } return 0; }错点：
1.break的位置应该放在外层while里，不能放在内层task.empty里面，否则死循环。
