Hexo

最小生成树

最短路径

有向无环图描述表达式

拓扑排序

// 有向图的拓扑排序
#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
*/

关键路径