70分求助!
  • 板块P2712 摄像头
  • 楼主PtrZ
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/4/21 20:47
  • 上次更新2023/11/5 00:16:04
查看原帖
70分求助!
206763
PtrZ楼主2021/4/21 20:47
//拓扑排序
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> e[20000];
queue <int> q;
int cnt[20000],ans=0;
void topo()
{
	for(int i=1;i<=n;i++)
	{
		if(!cnt[i])
		{
			q.push(i);
		}
	}
	while(!q.empty())
	{
		int v=q.front();
		//cout<<v<<endl;
		q.pop();
		
		ans++;
		int len=e[v].size();
		for(int i=0;i<len;i++)
		{
			int u=e[v][i];
			cnt[u]--;
			if(u>n) continue;
			if(!cnt[u])
			{
				q.push(u);
			}
		}
	}
}
int main() 
{
    cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x,y; cin>>x>>y;
		for(int j=1;j<=y;j++)
		{
			int tmp; cin>>tmp;
			e[x].push_back(tmp);
			cnt[tmp]++;
		}
	}
	topo();
	//for(int i=1;i<=n;i++) cout<<cnt[i]<<" ";
	//cout<<endl;
	if(ans==n)
	{
		cout<<"YES"<<endl;
	}
	else cout<<n-ans<<endl;
    return 0;
}
2021/4/21 20:47
加载中...