这题是不是可以用 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;
}