P2712 70pts求条
  • 板块灌水区
  • 楼主Z_L_H
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/18 20:42
  • 上次更新2024/10/18 22:41:07
查看原帖
P2712 70pts求条
1510234
Z_L_H楼主2024/10/18 20:42
#include<bits/stdc++.h>
using namespace std;
int read()
{
    char ch = getchar();
    int x = 0,f = 1;
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
int rd[100001];
bool a[5001][5001];
bool f[100001];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n;
	n = read();
	for(int i = 1;i <= n;i ++)
	{
		int x,m;
		x = read(),m = read();
		for(int i = 1;i <= m;i ++)
		{
			int y;
			y = read();
			f[x] = f[y] = true;
			a[x][y] = true;
			rd[y] ++;
		}
	}
	queue <int> q;
	for(int i = 1;i <= 500;i ++)
	{
		if(rd[i] == 0 && f[i])
		{
			q.push(i);
		}
	}
	while(!q.empty())
	{
		int t = q.front();
		q.pop();
		for(int i = 1;i <= n;i ++)
		{
			if(a[i][t] == true)
			{
				a[i][t] = false;
				rd[i] --;
				if(rd[i] == 0 && f[i])q.push(i);
			}
		}
	}
	int cnt = 0;
	for(int i = 1;i <= 500;i ++)
	{
		if(rd[i] != 0 && f[i])
		{
			cnt ++;
		}
	}
	if(cnt == 0)
	{
		cout<<"YES";
	}
	else
	{
		cout<<cnt;
	}
	return 0;
}

2024/10/18 20:42
加载中...