拓扑排序 算法应用

对于给定的有向无环图，给出一个序列满足对于图中的每条有向边 $(x,y)$ ，$x$ 在这个序列中都出现在 $y$ 之前

那么定义这个序列为这张图的一个拓扑序列

DFS处理拓扑序

DFS过程中会对每条路径都记录一次，利用 c 记录每个点的状态，$0,-1,1$ 分别表示 没有被访问过，被访问过，已经回溯过

如果存在一个DFS路径序，那么每个点的状态都会从 $0\to-1\to1$

DFS路径序是从出度为 $0$ 的点回溯记录的，翻转后得到拓扑序

vector<int> e[105];
vector<int> rnk;
int c[105];

bool dfs(int x){
    c=-1;//标记x点已经被访问过
    for (auto v:e){//尝试访问x的邻点
        if (c[v]==-1) return 0;//如果v已经被访问过，返回0
        if (!c[v])//如果没有被访问过
            if (!dfs(v)) return 0;//dfs到v点，如果v点返回0，连锁回溯
    }
    c=1;//回溯标记x点
    rnk.push_back(x);//记录路径序
    return 1;
}

bool toposort(void){
    memset(c,0,sizeof c);//初始化节点状态都为0
    for (int i=1;i<=n;i++)
        if (!c[i])//访问未标记的点
            if (!dfs(i)) return 0;//如果返回0，说明存在环，不存在路径序
    reverse(rnk.begin(),rnk.end());//翻转序列为拓扑序
    return 1;
}

Kahn算法处理

用队列维护一个入度为 $0$ 节点的集合，当一个节点 $y$ 的入度为 $0$ 时，此时该节点不被任何先序节点连接，即不存在未被访问过的有向边 $(x,y)$

需要对每个节点都记录它的入度 $dig_i$

int dig[105];
vector<int> rnk;

bool kahn(void){
    queue<int> q;
    for (int i=1;i<=n;i++)
        if (dig[i]==0)//初始状态将入度为0的节点加入队列
            q.push(i);
    while (q.size()){
        auto t=q.front();
        q.pop();
        rnk.push_back(t);//加入拓扑序
        for (auto v:e[t]){
            dig[v]--;//访问x,y有向边后，y节点入度-1
            if (dig[v]==0)//如果该节点入度为0
                q.push(v);//加入队列
        }
    }
    return rnk.size()==n;//如果拓扑序中元素个数大于节点数，说明存在环
}

bool f= kahn();
if (f)
    for (auto x:rnk) cout<<x<<' ';
else 
    cout<<-1<<endl;
return 0;

以洛谷P4017为例



const int mod=80112002;

int n,m;
vector<int> e[5010];
int cnt[5010];
int od[5010],id[5010];

int main()
{
    cintie;
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        e[a].push_back(b);
        od[a]++,id[b]++;//记录每个点的出度od和入度id
    }
    queue<int> q;
    for (int i=1;i<=n;i++){
        if (id[i]==0)
            q.push(i),cnt[i]=1;//将入度为0的节点加入队列，食物链初始化1
    }
    int ans=0;
    while (q.size()){
        auto t=q.front();
        q.pop();
        for (auto it:e[t]){
            cnt[it]=(cnt[it]+cnt[t])%mod;//累计当前节点的食物链数
            id[it]--;
            if (id[it]==0){
                if (od[it]==0)
                    ans=(ans+cnt[it])%mod;/如果走到了出度为0的节点（食物链端点），记录答案
                else 
                    q.push(it);//否则加入队列
            }
        }
    }
    cout<<ans;
    return 0;
}