算法笔记

1.利用dfs对DAG拓扑排序

当从某顶点v出发的DFS搜索完成时，v的所有后继顶点必定均已被访问过(想像它们均已被删除)，此时的v相当于是无后继的顶点，因此在DFS算法返回之前输出顶点v即可得到 DAG的逆拓扑序列。

模板（算法竞赛入门经典）：

 

int g[N][N];int vis[N];int topo[N];int t,n;bool dfs(int u){    vis[u]=-1;    for(int v=0;v

 2.队列实现拓扑排序，明显好理解

以下是判环版

bool topo_sort(int n){    q.clear();    int cnt=0;    for(int i=1;i<=n;i++){        if(tin[i]==0)cnt++,q.push(i);    }    while(!q.empty()){        int u=q.front();        q.pop();        for(int v:g[u]){            tin[v]--;            if(tin[v]==0)cnt++,q.push(v);        }    }    return cnt==n;}