70pts求助
  • 板块P2712 摄像头
  • 楼主LYqwq
  • 当前回复10
  • 已保存回复10
  • 发布时间2021/11/22 14:08
  • 上次更新2023/11/3 23:45:31
查看原帖
70pts求助
399116
LYqwq楼主2021/11/22 14:08
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n,x[505],m,y; // x直接用数组存,不用再开一个数组存哪些点有
int ind[505]; // 入度
int ans; // 记录已删除顶点数
queue<int> q; // 队列
vector<int> p[505]; // 邻接表

// 读写不多说
inline int read(){
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+ch-'0',ch=getchar();
	if(flag) return X;
	return ~(X-1);
}

inline void write(int X){
	if(X<0) putchar('-'),X=~(X-1);
	int s[20],top=0;
	while(X) s[++top]=X%10,X/=10;
	if(!top) s[++top]=0;
	while(top) putchar(s[top--]+'0');
	puts("");
}

void topo(){ // 拓扑排序
	for(int i=1; i<=n; i++){
		if(!ind[x[i]]){
			q.push(x[i]); // 入读为0的点push
		}
	}
	while(ans<n){ // 顶点没删完
		if(q.empty()){ // 队列为空,说明不能成功
			write(n-ans); // 输出
			exit(0);
		}
		int t=q.front();
		q.pop(); // 删除对头结点并存储
		for(int i=0,l=p[t].size(); i<l; i++){ // 遍历这个结点
			if(!--ind[p[t][i]]){ // 入读为0,push
				q.push(x[p[t][i]]);
			}
		}
		ans++; // 删除顶点数++
	}
	if(ans==n) puts("YES"); // 成功
}

int main(){
	n=read();
	for(int i=1; i<=n; i++){
		x[i]=read(),m=read(); // 读入不多说
		while(m--){
			y=read();
			p[x[i]].push_back(y);
			ind[y]++;
		}
	}
	topo();
	return 0;
}

调了一中午qwq,望大佬指导

2021/11/22 14:08
加载中...