有向无环图描述表达式

拓扑排序

// 有向图的拓扑排序
#include<bits/stdc++.h>
using namespace std;

map<int, vector<int> >mp;
int in[1000];
int out[1000];//表示入度和出度 
vector<int> ans;
vector<int> tail;

int n,m;

void topsort()
{
    //先找入度为0 其实可以认为这些都是起点
    stack<int>st;
    for(int i = 1;i<=n;i++)
    {
        if(in[i]==0)
        {
            st.push(i);
            ans.push_back(i);
        }
    }

    while(!st.empty())
    {
        int top = st.top();
        st.pop();
        // 以当前结点为起点的一系列点的入度都要减一 相当于解除限制了 如果为0就再添加进去
        for(int i = 0;i<mp[top].size();i++)
        {
            int tem = mp[top][i];
            in[tem]--;
            if(in[tem]==0)
            {
                st.push(tem);
                ans.push_back(tem);
            }
        }
    }
}

int main()
{
    // 顶点个数和边的个数
    cin >> n >> m;
    for(int i = 0;i<m;i++)
    {
        int u,v;
        cin >> u >> v;
        mp[u].push_back(v);
        in[v]++;
    }
    topsort();
    for(int i = 0;i<ans.size();i++)
    {
        cout << ans[i] <<" ";
    }
    return 0;
}/*
5 7
1 2
1 4
2 3
2 4
3 5
4 3
4 5
*/

void topsort()
{
    int num = 0;
    queue<int>q;// 存放度为0的结点
    for(int i = 0;i<n;i++)
    {
        if(degree[i]==0)
        {
            q.push(i);
            num ++;
        }
    }
    while(!q.empty()){
        int front = q.front();
        cout << front <<" ";
        q.pop();
        for(int i = 0;i<n;i++){//将该结点的所有出边的入度减1
            if(mp[front][i]!=0){
                degree[i]--;
                if(degree[i]==0)// 入度为0才可以入队
                {
                    q.push(i);
                    num++;
                }
            }
        }
    }

    if(num == n) cout << "\n拓扑排序成功!\n";
    else cout << "\n拓扑排序失败\n";

}

关键路径