用奇怪的方法90pts,求解!
查看原帖
用奇怪的方法90pts,求解!
1050431
DevilsFlame楼主2024/7/13 13:55
#include<bits/stdc++.h>
using namespace std;
vector <int> q[51000];
int s[51000],l[51000],v;
int n,x,m,ans;
inline void read(int &x){
	x=0;int y=1;
	char a=getchar();
	while(a>'9'||a<'0'){if(a=='-')y=-1;a=getchar();}
	while(a<='9'&&a>='0'){x=x*10+a-'0';a=getchar();}
	x*=y;
}
inline void write(int x)
{
	if(x > 9) write(x / 10);
	putchar(x % 10 + 48);
	return;
}
void dfs(int x)//看看监视对象能不能砸
{
	if(l[x]) return;
	bool e = 1;
	for(int i = 1;i <= n;i ++)//是否是监控
		if(s[i] == x)
		{
			e = 0;
			break;
		}
	if(e) return;
	ans ++;
	l[x] = -1;
	for(int i = 0;i < q[x].size();i ++)//看看这个对象
	{
		l[q[x][i]] --;
		dfs(q[x][i]);
	}
	return;
}
int main()
{
	read(n);
	for(int i = 1;i <= n;i ++)
	{
	    read(x),read(m);
	    s[i] = x;//记录这个地方是摄像头
	    while(m --)
	    {
	    	read(v);
	    	q[x].push_back(v);
	    	l[v] ++;
		}
	}
	for(int i = 1;i <= n;i ++)
	{
		int v = s[i];
		if(!l[v])
		{
			l[v] = -1;
			ans ++;//砸数++
			for(int j = 0;j < q[v].size();j ++)
				l[q[v][j]] --,dfs(q[v][j]);//看看监视对象能不能砸
		}
	}
	write(n - ans);
	return 0;
}
2024/7/13 13:55
加载中...