拓扑排序求助 1 2 10 wa
查看原帖
拓扑排序求助 1 2 10 wa
546159
lihansheng1楼主2023/10/22 12:56

rt,评测

#include<bits/stdc++.h>
using namespace std;
struct Node{
	long long v;
	long long u;
	long long next_;
};
long long head[1005];
bool head_jl[1005];
Node a[1005];
const long long NIL=-1;
long long d[1005];
int sum=0;
long long Index_=0;
long long n;
int maxn=0;
void Init_(){
	for(long long i=0;i<=1004;i++){
		head[i]=NIL;
		head_jl[i]=false;
	}
	return;
}
void add(long long u,long long v){
	d[v]++;
	a[Index_].next_=head[u];
	a[Index_].v=v;
	a[Index_].u=u;
	head[u]=Index_;
	head_jl[u]=true;
	Index_++;
}
int main(){
	Init_();
	cin>>n;
	for(int i=0;i<n;i++){
		int u;
		cin>>u;
		
		int num;
		cin>>num;
		for(int j=0;j<num;j++){
			int v;
			cin>>v;
			maxn=max(maxn,max(u,v));
			add(u,v);
		}
	}
	queue<int>q;
	for(int i=0;i<=maxn;i++){
		if(d[i]==0&&head_jl[i]==true){
			sum++;
			q.push(i);
		}
	}
	while(!q.empty()){
		int s=q.front();
		q.pop();
		for(int i=head[s];i!=-1;i=a[i].next_){
			d[a[i].v]--;
			if(d[a[i].v]==0&&head_jl[a[i].v]){
				q.push(a[i].v);
				sum++;
			}
		}
	}
	if(sum==n)cout<<"YES";
	else cout<<n-sum;
}
2023/10/22 12:56
加载中...