拓扑排序,但是输出一直是1
查看原帖
拓扑排序,但是输出一直是1
448126
Isa_wuyize楼主2024/4/13 11:13

我真菜

#include <bits/stdc++.h>
using namespace std;
int bigger[1001][1001],degree[1001],vis[1001],st[1001];
int qu[10000],top=0;
int main(){
	int n,m;cin>>n>>m;
	while(m--){
		int s;cin>>s;
		memset(vis,0,n);
		for(int i=0;i<s;i++){cin>>st[i];vis[st[i]]=1;}
		for(int i=1;i<=n;i++){
			if(vis[i]==0){
				for(int j=0;j<s;j++)
				if(bigger[st[j]][i]==0){bigger[st[j]][i]=1;degree[i]++;}
			}
		}
	}memset(vis,0,n);int cnt=0;
	do{
		top=0;
		for(int i=1;i<=n;i++){
			if(degree[i]==0&&vis[i]==0){qu[top]=i;top++;vis[i]=1;}
		}for(int i=1;i<=n;i++){
			for(int j=0;j<top;j++){
				if(bigger[qu[j]][i]){bigger[qu[j]][i]=0;degree[i]--;}
			}
		}cnt++;
	}while(top);
	cout<<cnt<<endl;
}

2024/4/13 11:13
加载中...