Ordering Tasks

链接

[https://vjudge.net/contest/281085#problem/D]

题意

有n个任务，有M个对先后顺序

然你输出最后的完成任务的顺序，有多种可能输出一种即可

分析

裸的拓扑排序,需要队列和vector

代码

#include<iostream>

#include<string.h>

#include<vector>

#include<queue>

using namespace std;

int n,m,a,b;

int in[110];

int main(){

	//freopen("in.txt","r",stdin);

	while(cin>>n>>m&&(n+m)){

		vector<int> v1[110];

		memset(in,0,sizeof(in));

		for(int i=1;i<=m;i++)

		{

			cin>>a>>b;

			v1[a].push_back(b);

			in[b]++;

		}

		queue<int> q;

		vector<int> v2;

		for(int i=1;i<=n;i++)

		if(in[i]==0) q.push(i);

		//cout<<q.size()<<endl;

		while(!q.empty()){

			int p=q.front();

			  q.pop();

			v2.push_back(p);

			for(int i=0;i<v1[p].size();i++){

				in[v1[p][i]]--;

				if(in[v1[p][i]]==0)

				q.push(v1[p][i]);

			}

		}

		for(int i=0;i<v2.size();i++)

		cout<<v2[i]<<' ';

		cout<<endl;

	}

	return 0;

}

巴特西

Ordering Tasks

链接

题意

分析

代码

最新文章

热门文章