AT_abc424_c.[ABC424C] New Skill Acquired

普及-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

高桥正在玩一个游戏。游戏中有 NN 个技能,编号为 11 到 NN。

你会得到 NN 对整数 (A1,B1),…,(AN,BN)(A_1,B_1),\dots,(A_N,B_N)。

如果 (Ai,Bi)=(0,0)(A_i,B_i)=(0,0),则高桥已经学会了技能 ii。
否则,高桥只有在技能 AiA_i 或技能 BiB_i 至少有一个已经学会的情况下,才能学习技能 ii。

请计算包括已经学会的技能在内,高桥最终能够学会多少个技能。

输入格式

输入从标准输入读入,格式如下:

NN
A1A_1 B1B_1
A2A_2 B2B_2
⋮\vdots
ANA_N BNB_N

输出格式

输出答案。

输入输出样例

  • 输入#1

    6
    0 0
    1 3
    3 2
    5 5
    4 6
    6 4

    输出#1

    3
  • 输入#2

    4
    0 0
    0 0
    0 0
    0 0

    输出#2

    4

说明/提示

样例解释 1

一开始,高桥已经学会了技能 11。因为技能 11 已经学会,所以技能 22 也可以学会,学会技能 22 后技能 33 也可以学会。由于无法学会技能 4,5,64,5,6,所以答案是 33。

数据范围

  • 1≤N≤2×1051\leq N \leq 2\times 10^5
  • (Ai,Bi)=(0,0)(A_i,B_i)=(0,0) 或 1≤Ai,Bi≤N1\leq A_i,B_i \leq N
  • 所有输入数据均为整数。

由 ChatGPT 5 翻译

输入解题思路,AI测评打分。不知道怎么写?

首页