70求调
  • 板块P2712 摄像头
  • 楼主tommy24
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/10 19:42
  • 上次更新2024/8/10 20:56:58
查看原帖
70求调
1419415
tommy24楼主2024/8/10 19:42
#include<bits/stdc++.h>
using namespace std;

//本体即计算有向图中非环形结构的顶点数 
//注意:松鼠的行走方式非线性,可以跳 

int n,x,y,t,res = 0;
int vis[510];

struct Node{//结构体定义有向图的顶点 
	int in;//记录入度 
	vector <int> out;//记录出边 
}a[510];

int main(){
	queue <int> q;//记录入度为0的区域 
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> x >> y;
		for(int j = 0; j < y; j++){
			cin >> t;
			a[x].out.push_back(t);//添加边(x,t) 
			a[t].in ++;//更新顶点t的入度 
		}
	}
	for(int i = 1; i <= n; i++){//遍历所有摄像头 
		if(!a[i].in){
			q.push(i);//将入度为0的顶点加入可拆除队列 
			vis[i] = 1;//记录可被拆除的摄像头 
		}
	}
	while(!q.empty()){
		t = q.front();
		q.pop();//拆摄像头
		for(int i = 0; i<a[t].out.size(); i++){//删除该顶点的所有出边 
			y = a[t].out[i];//需要删除的出边
			a[y].in--;//删除出边 
			if(!a[y].in){//更新出边两定点的入度,若入度为0,将该顶点加入可拆除队里 
				q.push(y);
				vis[y] = 1;
			}
		}
	}
	for(int i = 1; i <= n; i++){
		if(vis[i] == 1){
			res ++;
		}
	}
	if(res == n){
		cout << "YES";
	}else{
		cout << n - res;
	}
    return 0;
}

注释是笔记

2024/8/10 19:42
加载中...