题解：AT_abc424_c [ABC424C] New Skill Acquired

建一个有向图，对于

1 \le i \le N

，建两条有向边

A_i \to i

和

B_i \to i

，用

vis

标记每个点

i(A_i=B_i=0)

，接着将每个标记过的点深搜，搜索到的点全部打上标记（打过标记的点就是可以学会的技能），之后搜到就没必要继续往下搜了，最后统计标记点的数量输出即可。

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

O(N)

。

CPP

#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;
}

题解：AT_abc424_c [ABC424C] New Skill Acquired

文章操作

相关推荐

评论

题解：AT_abc424_c [ABC424C] New Skill Acquired