P10109 题解

WsW_ · 2024-01-30 00:37:00 · 题解

难度约为橙到黄。

本题解是目前题解区最精简的题解。

思路

对于每次合作：
假设合作的员工中有 x，那么 x 所有的领导都有可能成为主持者，给这些人的标记加一。
如果某个人的标记数等于 m，说明他是所有合作者的领导，那么他就可以当主持者。
在所有主持者中找到编号最大的即可。

可以使用 dfs 来遍历某个人所有的领导。

记得每次处理合作前要清空标记。

时间复杂度为 O(QN^2)。

代码

#include<bits/stdc++.h>
using namespace std;
int n,q,m,ans;
int f[300];
int cnt[300];
void dfs(int x){
    ++cnt[x];
    if(f[x]!=x)dfs(f[x]);//如果直接领导不是自己，就向上遍历
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++)cin>>f[i];
    cin>>q;
    while(q--){
        memset(cnt,0,sizeof(cnt));
        ans=0;
        cin>>m;
        for(int i=1;i<=m;i++){
            int x;  cin>>x;
            dfs(x);
        }
        for(int i=1;i<n;i++)if(cnt[i]==m)ans=i;
        cout<<ans<<'\n';
    }
    return 0;
}