题解：AT_abc424_c [ABC424C] New Skill Acquired

fengzhaoyu · 2025-09-26 16:50:58 · 题解

题意

就是有一些技能，得到技能 i 之前必须解锁其他两个技能 a_i，b_i 中的一个，问最后最多有几个技能。

思路

一开始就有的肯定是 a_i=b_i=0 的技能。

对于一个新解锁的技能 i，他能对技能 j 直接产生影响当且仅当 a_j 或 b_j 为 i。

然后就可以把已解锁技能放进一个队列，然后把凡是他能解锁的都解锁了，并放入队列，当然每个技能放一次（计算一次影响）就够了。

然后就没了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+15; 
int vis[N];
vector<int>g[N];
signed main()
{
    int n;
    cin>>n;
    queue<int>q;
    for(int i=1;i<=n;i++) 
    {
        int a,b;
        cin>>a>>b;
        if(a==b&&a==0)
        {
            q.push(i);
            continue;
        }
        g[a].push_back(i);//a做完就可以做i了
        if(a!=b)g[b].push_back(i);
    }
    int res=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        if(vis[u]) continue;
        res++;
        vis[u]=1;
        for(auto v:g[u])
        {
            if(vis[v]) continue;
            q.push(v);
        }
    }
    cout<<res<<endl;
    return 0;
}