70tps求助
  • 板块P2712 摄像头
  • 楼主Dcchen
  • 当前回复8
  • 已保存回复8
  • 发布时间2024/7/14 21:26
  • 上次更新2024/7/15 07:19:29
查看原帖
70tps求助
1012241
Dcchen楼主2024/7/14 21:26

平平无奇的拓扑排序,发现存的出度(out数组)好像没用到。求调!

#include<vector>
#include<queue>
#include<iostream>
using namespace std;
int n,m,u,v,ind[100005],out[100005],ans;
queue<int> q;
vector<int> p[100005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>u;
		cin>>m;
		for(int j=1;j<=m;j++){
			cin>>v;
			ind[v]++;
			out[u]++;
			p[u].push_back(v);
		}
	}
	for(int i=1;i<=n;i++){
		if(ind[i]==0){
			q.push(i);
		} 
	}
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=0;i<p[now].size();i++){
			int pos=p[now][i];
			ind[pos]--;
		}
	}
	for(int i=1;i<=n;i++){
		if(ind[i]<=0) ans++;
	}
	if(ans==n) cout<<"YES";
	else cout<<n-ans;
}
2024/7/14 21:26
加载中...