蒟蒻刚学图论90分求调玄关
  • 板块P2712 摄像头
  • 楼主shy_lihui
  • 当前回复10
  • 已保存回复10
  • 发布时间2024/8/13 14:50
  • 上次更新2024/8/13 16:37:09
查看原帖
蒟蒻刚学图论90分求调玄关
1053122
shy_lihui楼主2024/8/13 14:50
//#include<bits/stdc++.h>
#include<iostream>
#include<math.h>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<stdio.h>
using namespace std;
const int N=1e5+5;
vector<int> e[N];
int ind[N];
queue<int>q;
int n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int u,m;
		cin>>u;
		cin>>m;
		while(m--)
		{
			int v;
			cin>>v;
			e[u].push_back(v);
			ind[v]++;
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		if(ind[i]==0)
		{
			q.push(i);
			n--;
		}
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<e[u].size();i++)
		{
			int v=e[u][i];
			if(ind[v]!=0)
			{
				ind[v]--;
			}
			if(ind[v]==0)
			{
				q.push(v);
				n--;
			}
		}
	}
	if(n==0)
	{
		cout<<"YES";
	}
	else
	{
		cout<<n;
	}
	return 0;
}
2024/8/13 14:50
加载中...