题解：AT_abc424_c [ABC424C] New Skill Acquired

__QvQ__ · 2025-09-25 19:39:30 · 题解

前言

赛时苦战 1 个小时还是败给了 WA，看了同机房的大佬的 DFS 的解法后恍然大悟，故写此题解。

题目大意

有 N 种技能，给定 N 个数对 (A_1,B_1),\dots,(A_N,B_N)。如果 (A_i,B_i)=(0,0)，则已经学会了技能 i。否则，在技能 A_i 或技能 B_i 有至少一个学会时，技能 i 也会学习，最后求能学会的技能的总数。

解题思路

DFS 即可。

考虑每个技能的前置技能，声明 vec[i] 存储所有以 i 为前置的技能，当 (A_i,B_i)=(0,0) 或技能 i 已经学会时，那么直接 DFS 所有以 i 为前置的技能即可，同时还可以开一个标记数组因为当一个技能被搜索过时，所有以它为前置的技能都已被学会了，特别的，技能可以不按照输入顺序学习，最后复杂度是 O(N) 的，因为标记数组的原因没有重复搜索。

AC 代码

#include<bits/stdc++.h>
#define re ree()
#define pbk push_back
using namespace std;
long long ree(){long long f=1,k=0;char c=getchar();while(c<'0'||c>'9'){if(c == '-')f = -1;c=getchar();}while(c>='0'&&c<='9'){k=k*10+c-'0';c=getchar();}return f*k;}
long long n,m,k,bo[500010],cnt[500010],ans,vis[500010];
struct node{
    long long a,b,i;
}a[500100];
vector<int> vec[500010];
void dfs(int x)              //dfs 
{
    if(vis[x]!=0)
    {
        return;
    }
    ans++;
    vis[x]=1;
    for(int i=0;i<vec[x].size();i++)
    {
        dfs(vec[x][i]);
    }
    return;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        a[i].a=re;
        a[i].b=re;
        vec[a[i].a].pbk(i);
        vec[a[i].b].pbk(i);
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i].a==0&&a[i].b==0)
        {
            dfs(i);
        }
    }
    cout<<ans;
    return 0;
}