拓扑排序(深度优先) C++ 代码

拓扑排序(深度优先) C++ 代码

vector<int>g[N];//邻接表存储
int vis[N],topo[N],cnt;
bool dfs(int u)
{
    vis[u] = -1;//-1用来表示顶点u正在访问
    for(int i = 0 ; i < g[u].size() ; i ++)
    {
        if(vis[g[u][i]] == -1)//表示这个点进入了两次，肯定出现了环
            return false;
        else if(vis[g[u][i]] == 0)
        {
            dfs(g[u][i]);
        }
    }
    vis[u] = 1;
    topo[cnt++] = u;//放到结果数组里，输出的时候记得倒序输出，（回溯的原因）
    return true;
}
bool toposort(int n)
{
    memset(vis,0,sizeof(vis));
    for(int i = 1 ; i <= n ; i ++)
    {
        if(!vis[i])
        {
            if(!dfs(i)) return false;//huan
        }
    }
    return true;
}