提供一种新思路
查看原帖
提供一种新思路
1265459
little_stickman楼主2025/6/23 21:22

这题是不是可以用 BFS 来将一个员工可以管的人全部标记出来,再检查一下得出能不能用该员工的结论?最后如果没有员工,那么就让老板来。

这是我的 AC 代码:

#include <bits/stdc++.h>
using namespace std;

int n, m, f[310], a[310], used[310];

bool check()
{
	for(int i = 1;i <= m;i ++)
		if(!used[a[i]])
			return false;
	return true;
}

bool bfs(int v)
{
	queue<int> q;
	used[v] = 1;
	q.push(v);
	
	while(!q.empty())
	{
		int vv = q.front();
		q.pop();
		
		for(int i = 1;i < n;i ++)
			if(f[i] == vv && (!used[i]))
				q.push(i), used[i] = 1;
	}
	if(check())
		return true;
	else
		return false;
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	cin >> n;
	
	for(int i = 1;i < n;i ++)
		cin >> f[i];
	
	int Q;
	cin >> Q;
	
	while(Q --)
	{
		cin >> m;
		for(int i = 1;i <= m;i ++)
			cin >> a[i];
		
		bool fg = false;
		for(int i = n - 1;i >= 1;i --)
		{
			memset(used, 0, sizeof(used));
			used[i] = 1;
			if(bfs(i))
			{
				fg = true;
				cout << i << endl;
				break;
			}
		}
		if(!fg)
			cout << 0 << endl;
	}
	
	
	return 0;
}
2025/6/23 21:22
加载中...