文章

17

粉丝

166

获赞

6

访问

144.5k

头像
拓扑排序
P1566 中山大学2019年机试题
发布于2021年2月25日 14:45
阅读数 9.2k

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

int n, m;
vector<int> e[N];
vector<int> ans;
int d[N];//记录入度

bool topsort()
{
    priority_queue<int, vector<int>, greater<int>> q;

    for(int i = 1; i <= n; i++) if(!d[i]) q.push(i);

    while(q.size())
    {
        int t = q.top();
        q.pop();
        ans.push_back(t);

        for(int i = 0; i < e[t].size(); i++)
        {
            int j = e[t][i];
            if(-- d[j] == 0) q.push(j);
        }
    }
    return ans.size() == n;
}

int main()
{
    while(cin >> n >> m)
    {
		ans.clear();
		for(int i = 1; i <= N; i++ ) e[i].clear();
        while( m -- )
        {
            int a, b;
            cin >> a >> b;
            e[a].push_back(b);
            d[b] ++ ;
        }
        topsort();
        for(auto c : ans) cout << c << " ";
        cout << endl;
    }
  ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发