ABC424 C – New Skill Acquired

C - New Skill Acquired

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

はじめに（A, B）=（0, 0）の習得済みのスキルを持っておきました。また該当のスキルを習得している場合に習得できるスキルをdictで持ちます。

その後習得済みのスキルがあるだけループして、先ほどdictで持っておいたものの中から習得できるスキルを集める処理を書きました。

↓もっと書き方あると思いますが、ひとまず以下でACできました。

def i_map():
    return map(int, input().split())


def i_list():
    return list(map(int, input().split()))


n = int(input())
ab = [i_list() for _ in range(n)]
tmp = dict()
s = set()

for i in range(n):
    a, b = ab[i]
    if a == 0 and b == 0:
        s.add(i+1)
    else:
        if a in tmp:
            tmp[a].append(i+1)
        else:
            tmp[a] = [i+1]
        if b in tmp:
            tmp[b].append(i+1)
        else:
            tmp[b] = [i+1]

ans = set()
while len(s)!=0:
    x = s.pop()
    ans.add(x)
    if x in tmp:
        for y in tmp[x]:
            s.add(y)
        del tmp[x]

print(len(ans))Code language: Python (python)