题解：AT_abc424_c [ABC424C] New Skill Acquired

Luojt95 · 2025-09-26 18:49:06 · 题解

题目传送门。

AC记录。

建一个有向图，对于 1 \le i \le N，建两条有向边 A_i \to i 和 B_i \to i，用 vis 标记每个点 i(A_i=B_i=0) ，接着将每个标记过的点深搜，搜索到的点全部打上标记（打过标记的点就是可以学会的技能），之后搜到就没必要继续往下搜了，最后统计标记点的数量输出即可。

由于搜索时每个点最多只会被搜到一次，因此时间复杂度 O(N)。

#include<bits/stdc++.h>
using namespace std;
int n;
int a[200010],b[200010],vis[200010];
vector<int> e[200010];
void dfs(int x)
{
    if(vis[x]) return ;
    vis[x]=1;
    for(int i:e[x]) dfs(i);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        e[a[i]].push_back(i);
        e[b[i]].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]==0&&b[i]==0) dfs(i);
    }
    int ans=0;
    for(int i=1;i<=n;i++) if(vis[i]) ans++;
    cout<<ans;
    return 0;
}