ARC11B.Reversible Cards 해설 [pyhon]

URL

문제 개요

구속

코드 커밋

from collections import deque

n = int(input())
e = [[] for _ in range(4 * 10 ** 5 + 10)]  # 隣接リスト
for i in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a != b:
        e[a].append(b)
    e[b].append(a)
seen = [-1] * (4 * 10 ** 5)
# 連結成分に分解して、その中でmin(頂点の個数、辺の個数)を答えにたす
ans = 0
q = deque()
for i in range(4 * 10 ** 5):  # 全頂点：色に対して連結成分を数える
    if seen[i] == -1:
        q.append(i)
        num_e = 0
        num_v = 1
        num_t = 0
        # １つの連結成分に対して
        while q:
            now = q.popleft()
            seen[now] = 0
            for j in e[now]:
                num_e += 1
                if j == now:  # 自己辺
                    num_t += 1
                    continue
                if seen[j] == -1:
                    q.append(j)
                    seen[j] = 0
                    num_v += 1
        # print(e[i], num_e, num_v, i)
        ans += min((num_t + num_e) // 2, num_v)
print(ans)

고찰하다.

이루어지다