拓扑排序 求助90pts
  • 板块P2712 摄像头
  • 楼主Endline
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/8/13 10:49
  • 上次更新2023/10/27 15:39:29
查看原帖
拓扑排序 求助90pts
401052
Endline楼主2022/8/13 10:49
#include<bits/stdc++.h>
#define MAXN 502
#define int long long
using namespace std;
inline int read()
{
	int f=1,w=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')w=w*10+ch-'0',ch=getchar();
	return f*w;
}
vector<int>V[MAXN];
int n,x[102],ind[MAXN],cnt,f[MAXN];
void topo()
{
	queue<int>q;
	for(int i=1;i<=n;i++)if(ind[x[i]]==0)q.push(x[i]);
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		for(auto i:V[t])
			if(--ind[i]==0&&f[i])q.push(i),f[i]=false;
	}
}
signed main()
{
    n=read();
	for(int i=1;i<=n;i++)
	{
		x[i]=read();int m=read();
		f[x[i]]=true;
		for(int i=1;i<=m;i++)
		{
			int v=read();
			V[x[i]].push_back(v);
			ind[v]++;
		}
	}
	topo();
	for(int i=1;i<=n;i++)
		if(ind[x[i]]!=0)cnt++;
	if(cnt)printf("%lld\n",cnt);
	else puts("YES");
    return 0;
}
2022/8/13 10:49
加载中...