topsort 80分 求助
  • 板块P2712 摄像头
  • 楼主zbk_ning
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/12/13 21:29
  • 上次更新2023/12/14 10:56:12
查看原帖
topsort 80分 求助
851870
zbk_ning楼主2023/12/13 21:29
#include<bits/stdc++.h>
using namespace std;



const int N = 2000020;
const int mod=80112002;
int e[N], ne[N];//邻接表存储图
int h[N],in[N],out[N],a[N],v[N];
int num[N];
int idx=0;
int n, m;//保存图的点数和边数
queue<int> q; 

//topsort


void add(int a,int b){
	e[idx]=b;
	in[b]++;
	ne[idx]=h[a];
	h[a]=idx;
	idx++;
}




int main(){
	memset(h,-1,sizeof h);
	cin>>n;//摄像头个数 
	for(int i=1;i<=n;i++){
		int m,y;
		cin>>a[i]>>m;//摄像头位置;该摄像头能监控到的地方的个数 
		v[a[i]]=1;
		for(int j=1;j<=m;j++){
			cin>>y;
			add(a[i],y);
		}
	}
	
	for(int i=1;i<=n;i++){
		if(in[i]==0) q.push(a[i]);
	}
	int ans=0;
	while(q.size()){
		int tot=q.front();
		q.pop();
		if(v[tot]) ans++;
		
		for(int i=h[tot];i!=-1;i=ne[i]){
			int j=e[i];
			in[j]--;
			
			//有摄像头且入度为0 
			if(in[j]==0&&v[j]) q.push(j);
		}
	}
	
	if(ans==n) cout<<"YES";
	else cout<<n-ans;
	
	
}


2023/12/13 21:29
加载中...