拓扑排序25分求调
查看原帖
拓扑排序25分求调
1269111
Eden_star楼主2025/6/20 18:10
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,k,p,r;
int ans,cnt,rd[N];
queue<pair<int ,int >>q;
vector<int >pic[N];
int main(){
	cin>>n>>k>>p;
	for(int i=1;i<=p;i++){
		int x;
		cin>>x;
		q.push(make_pair(x,0));
		cnt++;
	}
	cin>>r;
	for(int i=1;i<=r;i++){
		int u,g,v;
		cin>>u>>g;
		for(int j=1;j<=g;j++){
			cin>>v;
			pic[v].push_back(u);
			rd[u]++;
		}
	}
	while(!q.empty()){
		int qq=q.front().first,t=q.front().second;q.pop();
		ans=max(ans,t);
		int len=pic[qq].size();
		for(int i=0;i<len;i++){
			int v=pic[qq][i];
			rd[v]--;
			if(!rd[v]){
				q.push(make_pair(v,t+1));
				if(v==k) cnt=n;
			}
		}
	}
	if(cnt==n) cout<<ans;
	else cout<<"-1";
}
2025/6/20 18:10
加载中...