拓扑排序

一、拓扑排序概念

对于一个有向无环图(DAG)，其拓扑排序是G中所有结点的一种线性次序，该次序满足如下条件：
如果图G包含边（u ，v），则结点u在拓扑排序中处于v结点的前面（如果图G包含环路，则不可能排出一个线性次序）。
可以将图的拓扑排序看做是将图的所有结点在一条水平线上排开，图的所有有向边都从左指向右

---

二、dfs拓扑排序实现

在任一有向无环图中，必然存在出度为0的顶点。否则，每个顶点都至少有一条出边，这意味着包含环路。
在对有向无环图的DFS搜索中，首先因访问完成而转换至VISITED状态的顶点m，其出度必然为0。

基于上述两条特性，我们可以得出结论：

DFS搜索过程中各顶点被标记为VISITED的次序，恰好（按逆序）给出了原图的一个拓扑排序。

1.无环

int in[maxn];
vector<int>g[maxn];
vector<int>ans;
int vis[maxn];

void dfs(int u){
    vis[u] = 1 ;
    for(auto v : g[u]){
        if(!vis[v]){
            vis[v] = 1 ;
            dfs(v);
        }
    }
    ans.pb(u);
}

void init(){
    ME(vis , 0);
}

void solve(){
    init();
    int n , m ;
    scanf("%lld%lld" , &n , &m);
    rep(i , 1 , m){
        int u , v ;
        scanf("%lld%lld" , &u , &v);
        g[u].pb(v);
    }
    rep(i , 1 , n){
        if(!vis[i])dfs(i);
    }
    red(i , size(ans)-1 , 0){
        cout << ans[i] << " ";
    }
}

signed main()
{
    solve();
}

2.判有环

dfs判断是否有环只需要把vis[]的状态改一下，原本是两种状态，0和1，现在改成0，1，-1,
0代表未访问，-1代表访问完毕，1代表是这一阶段正在访问的（这一阶段指的是两个元素在同一个递归中）。我只是列出改动的一部分。

void dfs(int u){
    vis[u] = 1 ;
    for(auto v : g[u]){
        if(vis[v] == 1){
            return 0 ;
        }else if(!vis[v] && !dfs(v)){
            return 0;
        }
    }
    vis[x] = -1;
    ans.pb(u);
    return 1 ;
}

---

三、bfs拓扑排序实现

1.记录每个结点的入度，将入度为0的结点放入队列.
2.取出队首结点，将该结点所有边连接的点入度减一.
3.重复1.2操作，直到队列为空.

1.可判有环

bool bfs(){
    vector<int>ans;
    priority<int>q;
    rep(i , 1 , n){
        if(!in[i]){
            q.push(i);
        }
    }
    while(!q.empty()){
        int u = q.top();q.pop();
        ans.pb(u);
        for(auto &v : g[u]){
            in[v]--;
            if(!in[v]){
                q.push(v);
            }
        }
    }
    if(size(ans) == n)//所有结点都入队了，无环。否则，最后图中存在环，找不到入度为0的点入队。
    {
        for(auto i : ans){
            cout << i << " " ;
        }
        return true;
    }else{
        return false;
    }
}