图搜索遍历你一种应用

针对有向图

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）。

1. 每个顶点出现且只出现一次；
2. 若A在序列中排在B的前面，则在图中不存在从B到A的路径。

也可以定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面。

可以证明（我不知道怎么证的），有向无环图一定存在一个拓扑序，所以有向无环图又称拓扑图

所以，所有当前入度为0的点，一定可以作为起点来判断

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], e[N], ne[N], idx;
int rd[N];

void init(){
    memset(h, -1, sizeof(h));
    idx = 0;
}

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void turpo(){
    queue<int> q;
    for(int i = 1; i <= n; i++){
        if(!rd[i]){
            q.push(i);
        }
    }
    
    vector<int> ans;
    
    while(!q.empty()){
        int f = q.front();
        
        q.pop();
        
        ans.push_back(f);
        
        for(int i = h[f]; i != -1; i = ne[i]){
            
            int j = e[i];
        
            rd[j]--;
            
            if(!rd[j])
                q.push(j);
            
        }
    }
    
    if(ans.size() == n){
        for(auto it : ans){
            cout << it << " ";
        }
    }
    else{
        cout << -1 << endl;
    }
}

int main(){
    init();
    
    scanf("%d%d",&n,&m);
    
    for(int i = 1; i <= m; i++){
        int a, b;
        scanf("%d%d",&a,&b);
        
        add(a, b);
        rd[b]++;
    }
    
    turpo();
    
    return 0;
    
}