拓扑排序求助
查看原帖
拓扑排序求助
580202
Siegerkranz_2735楼主2024/7/7 11:11

除了#1#5都re了 不知道哪里错了 求大佬

#include<bits/stdc++.h>
using namespace std;
int n,m,flag[1009],ind[1009],level[1009],ans;
int vec[1009][1009];
void topsort(){
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(ind[i]==0){
			q.push(i),level[i]=1;
		}
	}
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=1;i<=n;i++){
			if(vec[now][i]==0)continue;
			ind[i]--;
			if(ind[i]==0){
				level[i]=level[now]+1;
				ans=max(ans,level[i]);
				q.push(i);
			}
		}
	}
}
int main(){
	//freopen("b.in","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int s,fr,ta;cin>>s;
		queue<int> q;
		for(int j=1;j<=s;j++){
			int st;cin>>st;
			flag[st]=1;
			if(j==1)fr=st;
			if(j==s)ta=st;
		}
		for(int j=fr;j<=ta;j++)
			if(flag[j]==0)q.push(j);
		for(int j=fr;j<=ta;j++){
			if(flag[j]==1){
				flag[j]=0;
				int sens=q.front();
				q.pop();q.push(sens);
				(!vec[j][sens])&&(ind[sens]++,vec[j][sens]=1);
				for(;q.front()!=sens;){
					int now=q.front();
					q.pop();q.push(now);
					(!vec[j][now])&&(ind[now]++,vec[j][now]=1);
				}
			}
		}
	}
	topsort();
	cout<<ans;
	return 0;
} 
2024/7/7 11:11
加载中...