拓扑排序40pts求助!
查看原帖
拓扑排序40pts求助!
238885
Fat_Fish楼主2021/8/5 16:11

rt,评测记录,实在不知道哪里错了

#include<bits/stdc++.h>
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;
inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)) {
		if(ch=='-') {
			f=-1;
		}
		ch=getchar();
	}
	while(isdigit(ch)) {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int maxn=1e3+10;
int n,m,ind[maxn],a[maxn],d[maxn],ans,P[maxn];
vector<int> g[maxn];
void topo(){
	queue<int> q;
	for(int i=1;i<=n;++i){
		if(ind[i]==0){
			q.push(i);
			d[i]=1;
		}
	}
	while(!q.empty()){
		int u=q.front();q.pop();
		int len=g[u].size();
		for(int i=0;i<len;++i){
			int v=g[u][i];
			d[v]=max(d[v],d[u]+1);
			--ind[v];
			if(ind[v]==0){
				q.push(v);
			}
		}
	} 
	for(int i=1;i<=n;++i){
		ans=max(ans,d[i]);
	}
	return;
}
signed main() {
	n=read(),m=read();
	while(m--){
		memset(P,0,sizeof P);
		int k;
		k=read();
		for(int i=1;i<=k;++i){
			a[i]=read();
			P[a[i]]=1;
		}
		for(int i=a[1];i<=a[k];++i){
			if(P[i]==0){
				continue;
			}
			for(int j=i+1;j<=a[k];++j){
				if(P[j]==0){
					g[j].push_back(i);//j比i小 
					++ind[i];
				}
			}
		} 
	}
	topo();
	printf("%d\n",ans);
	return 0;
}
2021/8/5 16:11
加载中...