RT，我的第一份代码把级数和节点（停靠站的编号）一起作为结构体存入queue，第二份代码只在queue里存了节点，另开了一个数组解决了级数的问题。可以看到，两份代码只在拓扑排序部分有些许不同（如上描述），但第一份代码得了80pts，第二份代码却轻松AC。所以想请教一下大佬，这真的是queue的锅吗（我记得queue的插入和删除操作都是 $O(log\;n)$ 的吧）？

Code 1：

#include<bits/stdc++.h>
using namespace std;

int station[1005];
int vis[1005];
map<int,int> G[1005];
vector<int> g[1005];
int in_d[1005];

struct node{
	int num;//用num来记录级数
	int i;
};

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int sta;//station
		scanf("%d",&sta);
		memset(vis,0,sizeof(vis));
		memset(station,0,sizeof(station));
		for(int j=1;j<=sta;j++){
			scanf("%d",&station[j]);
			vis[station[j]]=1;
		}
		//建立有向无环图
		for(int j=station[1];j<=station[sta];j++){//从起点到终点
			if(vis[j]==0){//不是停靠点
				for(int k=1;k<=sta;k++){
					int a=j;
					int b=station[k];//从a向b连边
					if(G[a][b]==0){//防重边
						G[a][b]=1;
						g[a].push_back(b);
						in_d[b]++;
					}
				}
			}
		}
	}
	queue<node> q;
	for(int i=1;i<=n;i++){
		if(in_d[i]==0){
			q.push({1,i});
		}
	}
	int ans=0;
	while(!q.empty()){
		node t=q.front();
		q.pop();
		ans=max(ans,t.num);
		for(auto it=g[t.i].begin();it!=g[t.i].end();it++){
			in_d[*it]--;
			if(in_d[*it]==0){
				q.push({t.num+1,*it});
			}
		}
	}
	printf("%d",ans);
	return 0;
}

80pts的提交记录

Code 2：

#include<bits/stdc++.h>
using namespace std;

int station[1005];
int vis[1005];
int G[1005][1005];
vector<int> g[1005];
int in_d[1005];
int level[1005];

struct node{
	int num;//用num来记录级数
	int i;
};

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int sta;//station
		scanf("%d",&sta);
		memset(vis,0,sizeof(vis));
		memset(station,0,sizeof(station));
		for(int j=1;j<=sta;j++){
			scanf("%d",&station[j]);
			vis[station[j]]=1;
		}
		//建立有向无环图
		for(int j=station[1];j<=station[sta];j++){//从起点到终点
			if(vis[j]==0){//不是停靠点
				for(int k=1;k<=sta;k++){
					int a=j;
					int b=station[k];//从a向b连边
					if(G[a][b]==0){//防重边
						G[a][b]=1;
						g[a].push_back(b);
						in_d[b]++;
					}
				}
			}
		}
	}
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(in_d[i]==0){
			q.push(i);
			level[i]=1;
		}
	}
	int ans=0;
	while(!q.empty()){
		int t=q.front();
		q.pop();
		for(auto it=g[t].begin();it!=g[t].end();it++){
			in_d[*it]--;
			if(in_d[*it]==0){
				q.push(*it);
				level[*it]=max(level[*it],level[t]+1);//为了满足*it级数必须大于t，故取max
			}
		}
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,level[i]);
	}
	printf("%d",ans);
	return 0;
}

100pts的提交记录