ABC350 python Atcoderの記録

問題はこちら

A

S = input()
T = int(S[-3:])
flag = "No"
if 1<= T <= 315 or 317 <= T <= 349:
    flag = "Yes" 
print(flag)

N,Q = list(map(int, input().split()))
T = list(map(int, input().split()))
teeth = [0] + [1 for _ in range(N)] # 1-indexed
for t in T:
    if teeth[t] == 1:
        teeth[t] = 0
    else:
        teeth[t] = 1
print(sum(teeth))

N = int(input())
A = [0] + list(map(int, input().split()))
output = []
K = 0
while A != list(range(N+1)):
    for i in range(1, N):
        if A[i] != i:
            output.append([min(i,A[i]), max(i,A[i])])
            A[A[i]], A[i] = A[i], A[A[i]]
            
            K += 1
print(K)
for l in output:
    print(*l)
# print(A)

D
Union-Findを使えばよいらしい。要復習

zenn.dev

N, M = list(map(int, input().split()))

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n  # 各要素が属する部分木の要素数

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
            self.size[root_y] += self.size[root_x]
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
            self.size[root_x] += self.size[root_y]
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
            self.size[root_x] += self.size[root_y]
        return True

    def get_size(self, x):
        root = self.find(x)
        return self.size[root]

uf = UnionFind(N)

for _ in range(M):
    A, B = list(map(int, input().split()))
    A, B = A - 1, B - 1  # 0-indexedに修正
    uf.union(A, B)
    
# 最終的な根を求める
roots = set()
for i in range(N):
    roots.add(uf.find(i))
    
# 根から部分木の要素数を求める
max_edges = 0
for root in roots:
    n = uf.get_size(root)
    max_edges += n * (n - 1) // 2  # 整数の除算
# 現在の辺の数を引いて答えを算出
print(max_edges - M)