未知错误
查看原帖
未知错误
739899
p256rrq楼主2023/11/27 19:05

想用拓扑排序写

#include<bits/stdc++.h>
using namespace std;
int n,m;
int s,a;
vector<int>v;
vector<int>::iterator it;
bitset<1010>sta;
bool b[1010][1010];
queue<int>q;
int in[1010];
int lv[1010];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;++i)
	{
		cin>>s;
		for(int j=1;j<=s;++j)
		{
			cin>>a;
			v.push_back(a);
			sta[a]=1;
		}
		for(int j=1;j<=n;++j)
		{
			if(!sta[j])
			{
				for(it=v.begin();it<v.end();++it)
					b[*it][j]=true;
			}
				
			else sta[j]=0;
		}
		while(v.size()) v.pop_back();
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			if(b[j][i]) in[i]++;
		}
		if(in[i]==0)
		{
			q.push(i);
			lv[i]=1;
		}
	}
	while(q.size())
	{
		int f=q.front();
		q.pop();
		for(int i=1;i<=n;++i)
		{
			if(b[f][i])
			{
				in[i]--;
				lv[i]=lv[f]+1;
				if(!in[i]) q.push(i);
			}
		}
	}
	int ans=-1;
	for(int i=1;i<=n;++i)
	{
		ans=max(lv[i],ans);
	}
	cout<<ans<<'\n';
	return 0;
}
2023/11/27 19:05
加载中...