[编程题]任务调度
- 热度指数：1367 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
读入任务调度序列，输出n个任务适合的一种调度方式。
输入描述:
输入包含多组测试数据。
每组第一行输入一个整数n（n<100000），表示有n个任务。
接下来n行，每行第一个表示前序任务，括号中的任务为若干个后序任务，表示只有在前序任务完成的情况下，后序任务才能开始。若后序为NULL则表示无后继任务。
输出描述:
输出调度方式，输出如果有多种适合的调度方式，请输出字典序最小的一种。
示例1
输入
4 Task0(Task1,Task2) Task1(Task3) Task2(NULL) Task3(NULL)
输出
Task0 Task1 Task2 Task3
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
struct node{
string name;
vector<string> sons;
int number;
bool operator < (const node& A) const
{
if(this->number != A.number)
return this->number > A.number;
else
return this->name > A.name;
}
};
vector<node> v;
map<string, node> mp;
vector<string> vs;
void split(string s)
{
string t = "";
bool isFirst = 1;
vs.clear();
for(int i = 0 ;i<s.length();i++)
{
if(s[i] == '(' || s[i] == ')' || s[i] == ',')
{
if(t == "NULL")
{
break;
}
vs.push_back(t);
t = "";
continue;
}
t += s[i];
}
}
int main()
{
int n;
while(cin >> n)
{
mp.clear();
v.clear();
string s;
for(int i = 0 ; i<n;i++)
{
cin >> s;
split(s);
node t;
t.name = vs[0];
for(int j = 1;j<vs.size();j++)
{
t.sons.push_back(vs[j]);
}
t.number = 0;
mp[t.name] = t;
v.push_back(t);
}
for(int i = 0 ;i<v.size();i++)
{
node t = v[i];
for(int j = 0 ; j<t.sons.size();j++)
{
mp[t.sons[j]].number++;
}
}
priority_queue<node, vector<node> > q;
for(int i = 0 ;i<v.size();i++)
{
q.push(v[i]);
}
while(!q.empty())
{
node t = q.top();
q.pop();
for(int i = 0 ;i<t.sons.size();i++)
{
mp[t.sons[i]].number--;
}
cout << t.name ;
if(q.empty())
cout << endl;
else
cout << " ";
}
}
return 0;
}
发表于 2019-03-13 22:05:28
回复(2)
/*拓扑排序+最小堆*/
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#define N 100000
using namespace std;
int inDegree[N];
vector<int> M[N];//M[i]表示,i为M[i]下面所有结点相连的边的弧尾
priority_queue<int,vector<int>,greater<int>> Q;//构建最小堆，用于每次取出编号最小的任务
int getNo(string task){//获得任务的编号
int ans=0;
int c=1;
int len = task.size();
for(int i =len-1;i>=0;i--){
if('0'<=task[i]&&task[i]<='9'){
ans=ans+(task[i]-'0')*c;
}
else{
break;
}
c*=10;
}
return ans;
}
int main()
{
string str,substring;
int n,no,pos;
while(cin>>n){
for(int i=0;i<n;i++){
inDegree[i]=0;//初始化入度均为0
M[i].clear();//清空邻接链表
}
for(int i=0;i<n;i++){
cin>>str;
pos=0;//起始搜索位置
str.replace(str.find("("),1,",");
str.replace(str.find(")"),1,",");
while(1){//提取任务i的后续任务，并将其存储到任务i对应的链表当中
pos = str.find(",",pos+1);//找到第一个逗号的位置
if(str.find(",",pos+1)==string::npos)//如果后面还存在逗号
break;
else{//得到所有后续任务的编号
substring = str.substr(pos+1,str.find(",",pos+1)-pos-1);//获取目标字符串
if(substring=="NULL")continue;
M[i].push_back(getNo(substring));//构建有向图
}
}
}
//开始进行拓扑排序
for(int i=0;i<n;i++){
if(inDegree[i]==0)
Q.push(i);
}
while(!Q.empty()){
int node = Q.top();
Q.pop();
cout<<"Task"<<node<<" ";
for(int i=0;i<M[node].size();i++){
inDegree[M[node][i]]--;
if(inDegree[M[node][i]]==0)//如果上述操作产生了新的入度为0的结点，则将其插入最小堆当中
Q.push(M[node][i]);
}
}
cout<<endl;
}
return 0;
}
/*
4
Task0(Task1,Task2)
Task1(Task3)
Task2(NULL)
Task3(NULL)
*/
编辑于 2019-03-22 23:13:08
回复(0)
#include<cstdio>
#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include<map>
using namespace std;
struct node{ //定义优先队列节点及其优先法则
string task;
vector<string> sons;
int sons_number; //节点入度（忽略这个命名LOL，懒得改了）
friend bool operator < (const node &A,const node &B ){
if(A.sons_number!=B.sons_number)
return A.sons_number > B.sons_number; //入度越小优先级越高
else
return A.task > B.task; //入度相同，按字典序排列
}
};
priority_queue<node> q; //定义优先队列
map<string,node> mp; //用map记录每一个任务节点以便修改入度
string str;
int main(){
int n;
cin>>n;
getchar(); //注意下面要使用getline()；所以这里要读掉回车，
for(int i=0;i<n;i++){
getline(cin,str); //逐行读入并处理
int j=0;
while(str[j]!='(') j++;
string Task=str.substr(0,j); //读取前序任务
if(mp.find(Task)==mp.end()){ //该任务节点未建立则新建节点
node Node;
Node.sons_number=0;
Node.task = Task;
mp[Task] = Node ;
}
while(str[j]!=')'){ //处理后序任务节点的入度
j++;
int temp=j;
while(str[j]!=','&&str[j]!=')') j++;
if(str.substr(temp,(j-temp))!="NULL"){
mp[Task].sons.push_back(str.substr(temp,(j-temp)));
if(mp.find(str.substr(temp,(j-temp)))==mp.end()){//后序任务节点未建立则建立
node Node;
Node.task = str.substr(temp,(j-temp));
Node.sons_number=1;
mp[str.substr(temp,(j-temp))]=Node;
}else{
mp[str.substr(temp,(j-temp))].sons_number++;
}
}
}
q.push(mp[Task]);
}
for(int i=0;i<n;i++){
cout<<q.top().task<<' ';
node Node=q.top();
q.pop();
for(int i=0;i<Node.sons.size();i++){
mp[Node.sons[i]].sons_number--;
}
}
}
编辑于 2021-02-25 01:56:33
回复(0)
第一次自己写出来这代码，120行，刷新我的记录了。hah
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <climits>
using namespace std;
const int N = 1e5 + 20;
struct Node
{
string name;
vector<string> children;
bool operator < (Node a) const
{
return name > a.name;
}
}node[N];
map<string,Node> sN;
map<string,int> mymap;
bool vis[N];
vector<string> outs;
map<string,int> counts;
vector<string> vs;
vector<string> splits(string str)
{
vector<string> vs;
int start = 1;
string res;
bool flag = false;
while (1)
{
int k = str.find(",");
if (k == -1 )
{
if (flag == false)
vs.push_back(str.substr(1,str.size() - 2));
else
{
vs.push_back(str.substr(0, str.size() - 1));
}
break;
}
flag = true;
vs.push_back(str.substr(start, k - 1));
str = str.substr(k + 1);
start = k;
}
return vs;
}
int main()
{
int n = 0;
cin >> n;
string str;
getchar();
for(int i = 1; i <= n; i++)
{
getline(cin, str);
int index = 0;
for(int k = 0; k < str.size(); k++)
{
if(str[k] == '(')
{
index = k;
break;
}
}
string src = str.substr(0,index);
vs = splits(str.substr(index));
if(!mymap.count(src))
{
mymap[src] = 0;
}
for(int i = 0; i < vs.size();i++)
{
if(vs[i] != "NULL")
{
mymap[vs[i]]++;
}
else
break;
}
node[i].children = vs;
node[i].name = src;
sN[src] = node[i];
}
priority_queue<Node> q;
for(int i = 1; i <= n; i++)
{
if(mymap[node[i].name] == 0 )
{
q.push(node[i]);
}
}
while(q.size())
{
auto tmp = q.top();
q.pop();
outs.push_back(tmp.name);
for(int i = 0 ; i < tmp.children.size(); i++)
{
mymap[tmp.children[i]]--;
if(mymap[tmp.children[i]] == 0)
{
q.push(sN[tmp.children[i]]);
}
}
}
for(auto e: outs)
{
cout << e << " ";
}
cout <<endl;
}
发表于 2020-07-08 21:00:44
回复(0)
#include<iostream>
(720)#include<queue>
#include<algorithm>
(831)#include<vector>
using namespace std;
int n;
bool vist[100000]= {false};
vector<int> vt[100000];
void bfs() {
queue<int> q;
q.push(0);
vist[0]=true;
while(!q.empty()) {
int t=q.front();
q.pop();
printf("Task%d ",t);
for(int i=0; i<vt[t].size(); i++) {
if(vist[vt[t][i]]==false) {
q.push(vt[t][i]);
vist[vt[t][i]]=true;
}
}
}
}
int main() {
cin>>n;
getchar();
map<string,int> sti;
map<int,string> its;
string temp,t,org="Task";
for(int i=0,pos,pre; i<n; i++) {
getline(cin,temp);
t=temp.substr(0,5);
pre=t[4]-'0';
pos=6;
while(1) {
pos=temp.find(org,pos);
if(pos==-1) break;
t=temp.substr(pos,5);
pos++;
vt[pre].push_back(t[4]-'0');
}
}
bfs();
}
发表于 2020-04-03 10:53:59
回复(0)
学习别人的代码做出来的
#include<iostream>
(720)#include<vector>
#include<queue>
(789)#include<algorithm>
using namespace std;
const int MAX=1000;
int arr[MAX],dp[MAX];
int indegree[MAX];
vector<int> v[MAX];
priority_queue<int,vector<int>,greater<int>> Q;
int todigit(string s) {
int res=0,i=0;
while(i!=s.length()) {
if(isdigit(s[i])) res=res*10+s[i]-'0';
++i;
}
return res;
}
int main() {
string s;
int n;
while(cin>>n) {
for(int i=0; i<n; ++i) {
indegree[i]=0;
v[i].clear();
}
for(int i=0; i<n; ++i) {
cin>>s;
s.replace(s.find('('),1,",");
s.replace(s.find(')'),1,",");
int pos;
pos=s.find(',',0);
while(s.find(',',pos+1)!=s.npos) {
string str=s.substr(pos+1,s.find(',',pos+1)-pos-1);
if(str!="NULL") {
int num=todigit(str);
v[i].push_back(num);
++indegree[num];
} else break;
pos=s.find(',',pos+1);
}
}
for(int i=0; i<n; ++i) {
if(indegree[i]==0) Q.push(i);
}
int count=0;
while(!Q.empty()) {
++count;
int tmp=Q.top();
Q.pop();
cout<<"Task"<<tmp;
if(count==n) cout<<endl;
else cout<<" ";
for(int i=0;i<v[tmp].size();++i){
--indegree[v[tmp][i]];
if(indegree[v[tmp][i]]==0) Q.push(v[tmp][i]);
}
}
}
return 0;
}
发表于 2020-03-29 20:13:42
回复(0)
写了两个小时
#include<stdio.h>
#include<string.h>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
struct node
{
int no;//编号
int prior;
};
struct cmp
{
bool operator()(node a, node b)
{
if(a.prior!=b.prior) return a.prior > b.prior;//按照优先级
else return a.no > b.no;//按照名字
}
};
char a[1000001];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
getchar();
priority_queue<node, vector<node>, cmp> q;
map<int,int> p;//存放优先级
for(int i=0; i<n; i++)
{
scanf("%s",a);
int i1=4, n1=0;
while(a[i1]!='(')//第一个任务
n1=n1*10+a[i1++]-'0';
node t;
t.no = n1;
if(i==0)//是否是所有任务中的第一个
{
t.prior = 0;
q.push(t);
}
else
t.prior = p[t.no];
int i2= 6, n2=0;
if(a[i2]=='N')
continue;
while(i2 < strlen(a))
{
if(a[i2]>='0'&&a[i2]<='9') n2 = n2*10+a[i2]-'0';
if(a[i2]==','||a[i2]==')')
{
if(p[n2]==0)//队列中没有
{
node tt;
tt.no=n2;
tt.prior = t.prior+1;
q.push(tt);
n2 = 0;
p[n2]= tt.prior;
}
}
i2++;
}
}
while(q.size()>=1)
{
node t = q.top();
q.pop();
printf("Task%d ", t.no);
}
}
}
#include<string.h>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
struct node
{
int no;//编号
int prior;
};
struct cmp
{
bool operator()(node a, node b)
{
if(a.prior!=b.prior) return a.prior > b.prior;//按照优先级
else return a.no > b.no;//按照名字
}
};
char a[1000001];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
getchar();
priority_queue<node, vector<node>, cmp> q;
map<int,int> p;//存放优先级
for(int i=0; i<n; i++)
{
scanf("%s",a);
int i1=4, n1=0;
while(a[i1]!='(')//第一个任务
n1=n1*10+a[i1++]-'0';
node t;
t.no = n1;
if(i==0)//是否是所有任务中的第一个
{
t.prior = 0;
q.push(t);
}
else
t.prior = p[t.no];
int i2= 6, n2=0;
if(a[i2]=='N')
continue;
while(i2 < strlen(a))
{
if(a[i2]>='0'&&a[i2]<='9') n2 = n2*10+a[i2]-'0';
if(a[i2]==','||a[i2]==')')
{
if(p[n2]==0)//队列中没有
{
node tt;
tt.no=n2;
tt.prior = t.prior+1;
q.push(tt);
n2 = 0;
p[n2]= tt.prior;
}
}
i2++;
}
}
while(q.size()>=1)
{
node t = q.top();
q.pop();
printf("Task%d ", t.no);
}
}
}
发表于 2019-03-25 16:26:47
回复(0)
人生苦短
res = []
for _ in range(int(input())):
task = input()[:-1].replace('NULL', 'u').split('(') #-1去掉右括号,把NULL替换成u（比'Task'大就好），排序会靠后
res.append([task[0], sorted(task[1].split(','))]) #将后序任务也进行排序
res.sort(key=lambda x: (x[1], x[0])) #以后序任务为首要，再以前序任务为次要排序
print(" ".join(i[0] for i in res))
编辑于 2019-02-28 13:32:26
回复(0)
#include<stdio.h>//直接排序去掉括号内容即可
#include<string.h>
int main()
{
int n,i,j;
char a[1000][1000],b[1000];
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s",a[i]);
for(j=0;j<strlen(a[i]);j++)
if(a[i][j]=='(')
a[i][j]='\0';
}
for(i=0;i<n-1;i++)//冒泡
for(j=0;j<n-1-i;j++)
if(strcmp(a[j],a[j+1])>0)
{//交换
strcpy(b,a[j]);strcpy(a[j],a[j+1]);strcpy(a[j+1],b);
}
for(i=0;i<n;i++)
printf("%s ",a[i]);
}
编辑于 2020-04-09 11:37:15
回复(0)
#include <queue>//不需要优先队列！！！普通的一个拓扑排序而已，感觉有好多人写的太复杂了
#include <iostream>
#include <cstring>
using namespace std;
int arr[1000][1000], inde[1000], n;
void topology()
{
queue<int> q;
for (int j = 0; j < n; j++)
{
if (inde[j] == 0)
{
q.push(j);
}
}
while (!q.empty())
{
int p = q.front();
q.pop();
printf("Task%d ", p);
for (int j = 0; j < n; j++)
{
if (arr[p][j] != 0)
{
if ((--inde[j]) == 0)
q.push(j);
}
}
}
printf("\n");
}
int main()
{
while (cin >> n)
{
getchar();
string s;
memset(arr, 0, sizeof(arr));
memset(inde, 0, sizeof(inde));
for (int i = 0; i < n; i++)
{
getline(cin, s);
int from = s[4] - '0', to;
if (s[6] == 'N')
continue;
else
{
for (int j = 10; j < (int)s.size(); j += 6)
{
to = s[j] - '0';
arr[from][to] = 1;
inde[to]++;
}
}
}
topology();
}
system("pause");
return 0;
}
发表于 2021-03-20 11:49:02
回复(1)
不用拓扑排序的解***遇到这个反例：
4
Task0(Task2,Task3)
Task1(Task3)
Task2(NULL)
Task3(Task2)
画图可知输出结果是0 1 3 2而不是0 1 2 3
Task0(Task2,Task3)
Task1(Task3)
Task2(NULL)
Task3(Task2)
画图可知输出结果是0 1 3 2而不是0 1 2 3
发表于 2024-03-28 17:03:14
回复(0)
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
using namespace std;
const int MAX = 10001;
vector<int> graph[MAX];
int indegree[MAX];
vector<int> TopologicalSort(int n){
priority_queue<int, vector<int>, greater<int>> myqueue; //小的在前
for(int i=0; i<n; ++i){
if(indegree[i] == 0) myqueue.push(i); //从0开始
}
vector<int> ans; //记录序列
while(!myqueue.empty()){
int u = myqueue.top();
myqueue.pop();
ans.push_back(u);
for(int i=0; i<graph[u].size(); ++i){
int v = graph[u][i];
indegree[v]--;
if(indegree[v] == 0) myqueue.push(v);
}
}
return ans;
}
int main(){
int n;
while(cin >> n){
memset(graph, 0, sizeof(graph));
fill(indegree, indegree+n, 0);
int from, to;
string str;
for(int i=0; i<n; ++i){
cin >> str;
string temp;
int num;
for(int j=6; j<str.size()-1; ++j){
if(str[6]=='N') break;
if(str[j]>='0' && str[j]<='9'){
temp.push_back(str[j]);
if(str[j+1]==',' || str[j+1]==')'){
num = stoi(temp);
graph[str[4]-'0'].push_back(num);
indegree[num]++;
temp.clear();
}
}
}
}
vector<int> res = TopologicalSort(n);
for(int i=0; i<res.size(); ++i){
cout << "Task" << res[i] << ' ';
}
cout << endl;
}
}
发表于 2024-03-26 19:49:19
回复(0)
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<algorithm>
#define N 100005
using namespace std;
int n;
int indegree[N];//表示入度
vector<int> graph[N];//用来表示图的邻接表
vector<int> v1;
struct node {
int n;//表示结点序号
int degree;//表示度
};
priority_queue<node> pq;
bool operator < (node lhs, node rhs) {
return lhs.n > rhs.n;
}
void topology(string str) {
int flag = 0;
int a = str[4] - '0';
if (str[6] != 'N') {
for (int j = 10; j < str.size(); j++) {
if (isdigit(str[j])) {
graph[a].push_back(str[j] -'0'); //将某节点的后继结点放入邻接表中
indegree[str[j] -'0']++; //该结点是某个结点的后继结点，该结点的入度+1
}
}
}
}
int main() { //拓扑排序
//int n;
vector<string> vs;
while (cin >> n) {
for (int i = 0; i < n; i++) {
string str;
cin >> str;
topology(str);
}
for (int i = 0; i < n; i++) { //将度为零的结点入度
node no;
if (indegree[i] == 0) {
no.degree = 0;
no.n = i;
pq.push(no);
}
}
//sort(vz.begin(),vz.end());
while (!pq.empty()) { //将入读为0的结点出队，并且将遍历其后继结点其后继结点的入度-1，
int t = pq.top().n;
pq.pop();
cout << "Task" << t << " ";
for (int i = 0; i < graph[t].size(); i++) {
indegree[graph[t][i]]--;//对应结点入读-1
if (indegree[graph[t][i]] == 0) {
node no;
no.degree = 0;
no.n = graph[t][i];
pq.push(no);
}
}
}
}
}
发表于 2024-03-20 19:46:09
回复(0)
#include "bits/stdc++.h"
using namespace std;
inline int read() {
int x = 0, f = 1;
char c = getchar();
while (!(c <= '9' && c >= '0')) {
if (c == '-') {
f = -1;
}
c = getchar();
}
while (c <= '9' && c >= '0') {
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x * f;
}
int head[100005],cnt,n;
unordered_map<int,int>din;
vector<int>tp;
struct Edge{
int to,next;
}edge[100000*4];
void addedge(int u,int v){
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
bool toposort(){
priority_queue<int,vector<int>,greater<int>>q;
for(auto t:din){
if(t.second==0){
q.push(t.first);
//cout<<t.first<<endl;
}
}
while (!q.empty()){
auto t=q.top();
q.pop();
tp.push_back(t);
for(int i=head[t];i;i=edge[i].next){
int v=edge[i].to;
if(--din[v]==0){
q.push(v);
}
}
}
return tp.size()==n;
}
int main() {
n=read();
for(int i=1;i<=n;i++){
int u;
scanf("Task%d",&u);
din[u]=0;
string str;
getline(cin,str);
int x=0,flag=0;//flag=1表示正在读数字
for(int j=0;j<str.size();j++){
if(str[j]<='9' && str[j]>='0'){
flag=1;
x=(x<<3)+(x<<1)+(str[j]^48);
}else{
if(flag==1){
//cout<<u<<" "<<x<<endl;
addedge(u,x);
din[x]++;
flag=0;
}
x=0;
}
}
}
if(toposort()){
for(auto t:tp){
cout<<"Task"<<t<<" ";
}
}else{
//出现了环
exit(0);
}
return 0;
}
发表于 2023-08-13 15:14:38
回复(0)
比较复杂的一道题，图论的拓扑排序，加了字符串和定点数字的映射关系
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
vector<int> graph[100000];
unordered_map<string,int> task;
unordered_map<int,string> num;
string slist[100000];
int indegree[100000];
//将语句转化成图的边
void initial(string s){
int v=task[s.substr(0,s.find('('))];
s[s.size()-1]=',';
s=s.substr(s.find('(')+1);
do{
string temp=s.substr(0,s.find(','));
if(temp=="NULL"){
break;
}
int u=task[temp];
graph[v].push_back(u);
s=s.substr(s.find(',')+1);
}while(s!="");
}
int main() {
int n;
while(scanf("%d",&n)!=-1){
for(int i=0;i<n;i++){
cin>>slist[i];
string temp=slist[i].substr(0,slist[i].find('('));
task[temp]=i;
num[i]=temp;
}
for(int i=0;i<n;i++){
initial(slist[i]);
indegree[i]=0;
}
//到这一步，已经初始化好了图，任务名称与数字之间的互相映射关系
//由图初始化入度数组
for(int i=0;i<n;i++){
for(int j=0;j<graph[i].size();j++){
indegree[graph[i][j]]++;
}
}
//字典排序的优先队列
priority_queue<string,vector<string>,greater<string>> myqueue;
//入度为0的放到优先队列
for(int i=0;i<n;i++){
if(indegree[i]==0){
myqueue.push(num[i]);
}
}
while(!myqueue.empty()){
string temp=myqueue.top();
myqueue.pop();
//输出队列头
cout<<temp<<" ";
int v=task[temp];
//遍历队列头的出边，入度为0的放到优先队列
for(int i=0;i<graph[v].size();i++){
if(--indegree[graph[v][i]]==0){
myqueue.push(num[graph[v][i]]);
}
}
}
cout<<endl;
}
}
发表于 2023-02-26 17:00:52
回复(0)
#include"iostream"
#include"queue"
#include"map"
#include"string"
#include"vector"
using namespace std;
/* In degree table*/
map<string, int> inDegreeTab;
/* adjoin table*/
map<string, vector<string>> adjTab;
/* topological sorting*/
bool topologicalSorting(string &output){
int num= 0;
priority_queue<string, vector<string>, greater<string>> myQueue;
// ls inDegreeTab
for(map<string, int>:: iterator it= inDegreeTab.begin(); it!= inDegreeTab.end(); it++){
if(it->second== 0){
myQueue.push(it->first);
num++;
}
}
// bianli
while(!myQueue.empty()){
string task= myQueue.top();// pop
myQueue.pop();
output= output +" " +task;// add into load
vector<string> v= adjTab[task];
for(int i= 0; i< v.size(); i++){
inDegreeTab[v[i]]--;
if(inDegreeTab[v[i]]== 0){
myQueue.push(v[i]);
num++;
}
}
}
// ret
if(output.length()>0){output= output.substr(1);}
return num== inDegreeTab.size();
}
int main(){
int n;
while(cin>> n){
// init inDegreeTab、adjTab
inDegreeTab.clear();
adjTab.clear();
// input
string ipt;
for(int i= 0; i< n; i++){
cin>> ipt;// task0
string t1= ipt.substr(0, ipt.find('('));
ipt= ipt.substr(ipt.find('('));// (task1,task2)
ipt= ipt.substr(1, ipt.length()-2); // remove () >> task1,task2
ipt= ipt+ ",";// task1,task2,
// init degree tab
if(inDegreeTab.count(t1)== 0){
inDegreeTab[t1]= 0;// no find insert
}
if(adjTab.count(t1)== 0){
adjTab[t1]=vector<string>(0);// ji ling ghost
}
while(ipt!=""){
string t= ipt.substr(0, ipt.find(',')+ 1);// task1,
t= t.substr(0, t.length()- 1);// task1
ipt= ipt.substr(ipt.find(',')+ 1);//task2,..,
if(t!="NULL"){// init adjoin table and indegree tab
adjTab[t1].push_back(t);
inDegreeTab[t]++;
}
}
}
// topologicalSorting
string opt;
if(topologicalSorting(opt)){
cout<< opt<<endl;
}
}
}
发表于 2021-03-09 15:42:43
回复(0)
图采用邻接表法，代码可复用性强
#include<iostream>
#include<unistd.h>
#include<vector>
#include<map>
using namespace std;
struct Node{
Node* next;
string name;
Node(string task_name):name(task_name),next(nullptr){}
void insert(string task_name){
if(task_name=="NULL") return;
Node* n = new Node(task_name);
n->next = this->next;
this->next = n;
}
bool is_in_next_list(string task_name){
Node* h = next;
while(h!=nullptr){
if(h->name==task_name){
return true;
}
}
return false;
}
void erase(string task_name){
Node* h = this;
while(h->next!=nullptr){
if(h->next->name==task_name){
Node* temp=h->next;
h->next = temp->next;
delete temp;
return;
}
h=h->next;
}
}
};
struct Graph{
Graph(){}
~Graph(){
for(int i=0;i<m_edge.size();i++){
Node* head = m_edge[i];
while(head!=nullptr){
Node* temp = head->next;
delete head;
head=temp;
}
}
}
void insert(Node* n){
auto it = m.find(n->name);
if(it==m.end()){
m_edge.push_back(n);
m[n->name]=n;
return;
}
Node* edgeNode = it->second;
n=n->next;
while(n!=nullptr){
Node* temp = n->next;
if(edgeNode->is_in_next_list(n->name)){
delete n;
n=temp;
continue;
}
//头插法
n->next = edgeNode->next;
edgeNode->next=n;
n=temp;
}
}
bool hasPre(string task_name){
for(int i=0;i<m_edge.size();i++){
Node* h = m_edge[i]->next;
while(h!=nullptr){
if(h->name==task_name) return true;
h=h->next;
}
}
return false;
}
void erase(string task_name){
auto it = m.find(task_name);
if(it!=m.end()) m.erase(it);
//遍历每个边表节点
vector<Node*>::iterator iter;
int flag=0;
for(auto it=m_edge.begin();it!=m_edge.end();it++){
if((*it)->name==task_name){
delete *it;
flag=1;
iter = it;
continue;
}
Node* edge_node = *it;
edge_node->erase(task_name);
}
if(flag==1) m_edge.erase(iter);
}
void topological_sort(){
for(int i=0;i<m_edge.size();i++){
string name = m_edge[i]->name;
if(hasPre(name)) continue;;
cout<<name<<" ";
erase(name);
break;
}
if(m_edge.size()==0){cout<<endl;return;}
topological_sort();
}
private:
vector<Node*> m_edge; //边表节点
map<string,Node*> m;
};
string get_next_task(const string& input,int& start){
for(int i=start;i<input.size();i++){
if(input[i]=='N'){
start=i+4;
return input.substr(i,4);
}
if(input[i]=='T'){
start=i+5;
return input.substr(i,5);
}
}
return "";
}
int main(){
int n;
string input;
cin>>n;
Graph g;
while(n--){
cin>>input;
Node* edgeNode = new Node(input.substr(0,5));
int start=6;
string task_name;
while((task_name = get_next_task(input,start))!=""){
edgeNode->insert(task_name);
}
g.insert(edgeNode);
}
g.topological_sort();
return 0;
}
编辑于 2021-03-02 13:16:36
回复(0)
一开始一度以为这道题要用拓扑排序求解，以至于搞了半天入度出度表。。结果只要把后续任务优先级简单加一就行了。
这道题的题设并不严谨，它没有说明输入的任务也是按字典序排序的，优先级简单加一仅适用于任务序号依次增加的情况，如图所示：
这是关于这道题的一些问题，仅是个人的思考。
#include <bits/stdc++.h>
using namespace std;
struct task{
int tno;
int priority;
task(){
tno = 0;
priority = 0;
}
friend bool operator < (const task &t1, const task &t2){
if(t1.priority!=t2.priority)
return t1.priority>t2.priority;
else
return t1.tno > t2.tno;
}
}taskList[100010];
bool isLeagle(char c){
if((c>='a'&&c<='z')||(c>='A'&&c<='Z')||(c>='0'&&c<='9'))
return true;
else return false;
}
int main() {
int n;
while(scanf("%d" ,&n)!=EOF){
priority_queue<task> q;
for(int i=0; i<n; i++){
string str;
cin>>str;
for(int j=0; j<str.size(); j++){
if(!isLeagle(str[j]))
str[j] = ' ';
}
stringstream Str;
Str.str(str);
string tok;
getline(Str, tok, ' ');
int t = tok[4] - '0';
taskList[t].tno = t;
while(getline(Str, tok, ' ')){
if(tok!="NULL")
taskList[tok[4] - '0'].priority = taskList[t].priority+1;
}
}
for(int i=0; i<n; i++){
q.push(taskList[i]);
}
while(q.size()>=1){
task t=q.top();
q.pop();
printf("Task%d ",t.tno);
}
printf("\n");
}
return 0;
}
发表于 2021-02-02 10:57:41
回复(0)
/*
字符串处理+拓扑排序（使用优先队列使其按字典排序）
按题意，图中无环
*/
#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
struct Node {
int indgree;
vector<string> sub_tasks;
string name;
bool operator < (const Node& n) const {
if (indgree != n.indgree) return indgree > n.indgree;
else return name > n.name;
}
};
map<string, Node> graph;
int main() {
int n;
while (cin >> n) {
string tasks;
while (n--) {
cin >> tasks;
int left = tasks.find('(');
int right = tasks.find(')');
string priority = tasks.substr(0, left);
string sub_task = tasks.substr(left + 1, right - left - 1);
Node node;
node.name = priority;
node.indgree = 0;
node.sub_tasks.clear();
if (sub_task != "NULL") {
string sub;
for (int i = 0; i < sub_task.size(); i++) {
if (sub_task[i] == ',') {
node.sub_tasks.push_back(sub);
sub.clear();
continue;
}
sub += sub_task[i];
}
node.sub_tasks.push_back(sub);
}
graph[node.name] = node;
}
for (auto i = graph.begin(); i != graph.end(); i++) {
for (auto j : i->second.sub_tasks) {
graph[j].indgree++;
}
}
priority_queue<Node> q;
for (auto i = graph.begin(); i != graph.end(); i++) {
if(i->second.indgree==0)
q.push(i->second);
}
int count = 0;
while (!q.empty()) {
Node node = q.top();
q.pop();
count++;
for (auto i : node.sub_tasks) {
graph[i].indgree--;
if (graph[i].indgree == 0)
q.push(graph[i]);
}
cout << node.name;
if (q.empty())cout << endl;
else cout << " ";
}
//if (count == graph.size())cout << "YES" << endl;
}
return 0;
}
发表于 2020-07-02 12:11:14
回复(0)
并查集
#include<iostream>
(720)#include<string>
#include<vector>
(721)#define N 100000
using namespace std;
int root[N];
int n;
vector<int> v;
int main(){
cin>>n;
string str;
for(int i=0;i<n;i++)
root[i]=-1;
for(int i=0;i<n;i++){
cin>>str;
int p=0;
int j;
for(j=str.find("k")+1;str[j]>='0'&&str[j]<='9';j++)
p=10*p+str[j]-'0';
str=str.substr(j+1,str.length());
while(str.find("k")!=str.npos){
int child=0;
for(j=str.find("k")+1;str[j]>='0'&&str[j]<='9';j++)
child=10*child+str[j]-'0';
root[child]=p;
str=str.substr(j+1,str.length());
}
}
while(v.size()!=n){
for(int i=0;i<n;i++){
if(root[i]==-1)
v.push_back(i);
root[i]=-2;//标识i号被删除了
for(int j=0;j<n;j++){
if(root[j]==i)
root[j]=-1;
}
}
}
for(int i=0;i<n;i++){
if(i==0)
cout<<"Task"<<v[i];
else
cout<<" Task"<<v[i];
}
return 0;
}
发表于 2020-04-07 10:52:23
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
