文章

60

粉丝

361

获赞

43

访问

524.5k

头像
打卡
P1566 中山大学2019年机试题
发布于2021年1月26日 17:22
阅读数 7.4k

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

int len[maxn];
vector<int>a[maxn];

priority_queue <int ,vector<int>,greater<int>>q;
void topo(int n)
{
	for(int i=1;i<=n;i++)
		if(!len[i])q.push(i);
	int flag=0;
	while(!q.empty())
	{
		int now=q.top();
			q.pop();
		if(flag)cout<<" "<<now;
		else cout<<now;
		flag++;
		for(int i=0;i<a[now].size();i++)
		{
			int next=a[now][i];
			len[next]--;
			if(!len[next])q.push(next);
		}
	}
}

int main()
{
	int n,m;
	while(cin>>n>>m)
	{
		memset(len,0,sizeof(len));
		for(int i=0;i<maxn;i++)
			a[i].clear();

		for(int i=0;i<m;i++)
		{
			int x,y;
			cin>>x>>y;
			a[x].push_back (y);//记录顶点的相邻边
			len[y]++;//记录入度
		}
		topo(n);
		cout<<endl;
	}
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发