70分,求调
  • 板块P2712 摄像头
  • 楼主gaozihe
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/6/22 19:17
  • 上次更新2025/6/23 19:18:20
查看原帖
70分,求调
1495949
gaozihe楼主2025/6/22 19:17
#include <bits/stdc++.h>
#define MAXN 100000
#define MAXM 20000000
using namespace std;
int n,head[MAXN],ans=-9999,tot=1,indegree[MAXN],sh[MAXN];
queue<int> q;
struct node{
	int to,nxt;
}edge[MAXM];
void addedge(int a,int b){
	edge[tot].to=b;
	edge[tot].nxt=head[a];
	head[a]=tot;
	indegree[b]++;
	tot++; 
}
int topsort(){
	int temp=0;
	for(int i=1;i<=n;i++){
		if(indegree[i]==0&&sh[i]==1){
			q.push(i);
		}
	}
	while(!q.empty()){
		for(int k=head[q.front()];k;k=edge[k].nxt){
			int v=edge[k].to;
			indegree[v]--;
			if(indegree[v]==0){
				q.push(v);
			}
		}
		temp++;
		//cout<<q.front()<<' ';
		q.pop();
	}
	//cout<<endl;
	return temp;
}
int main(){
	memset(sh,0,sizeof(sh));
	memset(head,0xff,sizeof(head));
	memset(indegree,0,sizeof(indegree));
	cin>>n;
	for(int i=1;i<=n;i++){
		
	//	memset(ans1,0,sizeof(ans1));
		int x,m;
		cin>>x>>m;
		sh[x]=1;
		for(int i=1;i<=m;i++){
			int y;
			cin>>y;
			addedge(x,y);
		}
	}
	int p=topsort();
	if(p==n) cout<<"YES"<<endl;
	else
	cout<<(n-p)<<endl;
	return 0;
}
2025/6/22 19:17
加载中...