[ABC424C]New Skill Acquired题解

摘要：问题描述了一个技能学习系统，其中初始已学会(0,0)标记的技能。通过BFS遍历，当某个技能的依赖技能(Ai或Bi)被学会时，该技能即可被学习。给定N个技能及其依赖关系，要求计算最终可学会的技能总数。算法使用队列处理已学会技能，并检查其能解锁的新技能，时间复杂度为O(N)。示例1中初始学会技能1，通过依赖链最终学会3个技能。

bz02_2023f2

180人浏览 · 2025-09-30 16:18:16

bz02_2023f2 · 2025-09-30 16:18:16 发布

时间限制：2 秒 / 内存限制：1024 MiB

得分： 300 分

《A - 回文数》《A - 回文数》《A - 回文数》

问题描述

高桥正在玩一个游戏。这个游戏有编号为 1 到 N 的 N 个技能。

给你 N 对整数 (A1,B1),…,(AN,BN) 。
如果 (Ai,Bi)=(0,0) ，那么高桥已经学会了技能 i 。
否则，高桥能够学会技能 i 的条件是，技能 Ai 和 Bi 中至少有一个已经被学会。

包括已经掌握的技能，找出高桥最终可以学习的技能数量。

《A - 回文数》《A - 回文数》《A - 回文数》

约束条件

1≤N≤2×105
(Ai,Bi)=(0,0) 或 1≤Ai,Bi≤N
所有输入值都是整数。

《A - 回文数》《A - 回文数》《A - 回文数》

输入

输入从标准输入中按以下格式给出：

N
A1 B1
A2 B2
⋮
AN BN

《A - 回文数》《A - 回文数》《A - 回文数》

输出

输出答案。

《A - 回文数》《A - 回文数》《A - 回文数》

示例输入 1 复制

复制

《A - 回文数》《A - 回文数》《A - 回文数》

示例输出 1 复制

复制

最初，高桥已经学习了技能 1 。因为技能 1 已经被学习，所以可以学习技能 2 ，学习技能 2 可以学习技能 3 。由于不可能学习技能 4,5,6 ，所以答案是 3 。

《A - 回文数》《A - 回文数》《A - 回文数》

样本输入 2 复制

复制

《A - 回文数》《A - 回文数》《A - 回文数》

样本输出 2 复制

复制

思路

考虑bfs，首先加入学会的知识，然后，若根据这个知识能学会某知识且该知识未学，则加入队列，并标记。

代码见下

#include<bits/stdc++.h>
using namespace std;
long long n,a[200005],b[200005],f[200005],lk=0;
vector<long long> v[200005];
queue<long long> q;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		if(a[i]==0&&b[i]==0){
			f[i]=2;
			q.push(i);
		}
		else{
			v[a[i]].push_back(i);
			v[b[i]].push_back(i);
		}
	}
	while(q.size()>=1){
		long long qa=q.front();
		q.pop();
		for(int i=0;i<v[qa].size();i++){
			long long tt=v[qa][i];
			f[tt]++;
			if(f[tt]==1){
				q.push(tt);
			}
		}
	}
	lk=0;
	for(int i=1;i<=n;i++){
		if(f[i]>=1){
			lk++;
		}
	}
	cout<<lk<<endl;
	return 0;
}