拓扑排序的dfs写法

dfs深搜+时间戳的应用

有关时间戳：
时间戳可以记录dfs的生存周期，祖先与后代的时间戳之间一定存在这样的关系：
祖先的[dtime,ftime]一定包含后代的[dtime,ftime],因此，可以用时间戳来判负环
当出现后代指向祖先的边时，祖先的dtime<后代的dtime,祖先的ftime还没更新

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=100010;

int n,m;
int h[N],e[N],ne[N],idx;//建图
bool st[N];
int deg[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    deg[b]++;
}


int dtime[N],ftime[N],clk;//时间戳(记录节点在dfs中的生命周期)
bool flag=true;

stack<int> res;//在dfs的写法中，得到的是拓普序列的逆序，用栈来进行逆序输出

void topSort(int x){//dfs写法的拓扑序
    dtime[x]=clk++;
    st[x]=true;
    for(int i=h[x];i!=-1;i=ne[i]){
        int y=e[i];
        if(st[y]==true){
            if(ftime[y]==-1)//如果dtime(y)<dtime(x)&&ftime(y)>ftime(x)的话，则y是x的祖先
                flag=false;//如果存在后代指向祖先的边，则图中存在环
            continue;
        }
        topSort(y);
    }
    res.push(x);
    ftime[x]=clk++;
}

int main(){
    memset(ftime,-1,sizeof ftime);
    memset(h,-1,sizeof h);
    cin>>n>>m;
    while(m--){//输入
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    //cnt用来检验输入了一个环的特殊情况（但acwing上没有这样的特殊数据）
    int cnt=0;
    for(int i=1;i<=n;i++){//从每个入度为0的点出发进行dfs
        if(deg[i]==0){
            cnt=1;
            topSort(i);
        }
    }
    if(!cnt) flag=false;
    //输出
    if(!flag) puts("-1");
    else{
        while(res.size()){
            cout<<res.top()<<" ";
            res.pop();
        }
    }

}