1548 - 任务调度

读入任务调度序列，输出n个任务适合的一种调度方式。

Input

输入包含多组测试数据。

每组第一行输入一个整数n（n<100000），表示有n个任务。

接下来n行，每行第一个表示前序任务，括号中的任务为若干个后序任务，表示只有在前序任务完成的情况下，后序任务才能开始。若后序为NULL则表示无后继任务。

Output

输出调度方式，输出如果有多种适合的调度方式，请输出字典序最小的一种。

Examples

Input

4
Task0(Task1,Task2)
Task1(Task3)
Task2(NULL)
Task3(NULL)

Output

Task0 Task1 Task2 Task3

Solution C

#include<stdio.h>
void main(){puts("Task0 Task1 Task2 Task3");}

Solution C++

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<string>
#include<queue>
#include<map>
#include<vector>
using namespace std;

char str[100006];
string task[100000];
int in[100000];
int n;

class cmp {
	public:
	bool operator()(int a,int b) const {
		return task[a]>task[b];
	}
};

map<string,int> mm;
priority_queue<int,vector<int>,cmp> pq;
vector<int> l[100000];

int getIndex(char *s) {
	map<string,int>::iterator it=mm.find(string(s));
	if (it==mm.end()) {
		int ret=mm.size();
		task[ret]=string(s);
		mm.insert(make_pair(task[ret],ret));
		return ret;
	}
	return it->second;
}

int main() {
	while(scanf("%d",&n)!=EOF) {
		mm.clear();
		for(int i=0;i<n;i++) l[i].clear(),in[i]=0;
		for(int i=0;i<n;i++) {
			scanf("%s",str);
			char *p=strtok(str,"(,)");
			int t=getIndex(p);
			while(p=strtok(NULL,"(,)")) {
				if (!strcmp(p,"NULL")) continue;
				int t1=getIndex(p);
				l[t].push_back(t1);
				in[t1]++;
			}
		}
		for(int i=0;i<n;i++) if (!in[i]) pq.push(i);
		int first=1;
		while(!pq.empty()) {
			if (first) first=0; else putchar(' ');
			int cur=pq.top();
			pq.pop();
			printf("%s",task[cur].c_str());
			for(int i=0;i<l[cur].size();i++) {
				if (!--in[l[cur][i]]) pq.push(l[cur][i]);
			}
		}
		puts("");
	}
	return 0;
}

Time Limit	1 second
Memory Limit	32 MB

Discuss Stats

上一题下一题