ABC293D - Tying Rope

考え方1

閉路ができたかどうかをUnionFind木で見る（閉路検出 - 競プロはじめました）．

N, M = map(int, input().split())
# --- UnionFind ---
p = [-1] * (N + 1)
def root(x):
    if p[x] < 0:
        return x
    p[x] = root(p[x])
    return p[x]
 
def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    p[x] += p[y]
    p[y] = x

def size(x):
    x = root(x)
    return -p[x]
# --- UnionFind ---

loop = 0
for _ in range(M):
    a, b, c, d = input().split()
    a = int(a) - 1
    c = int(c) - 1
    if root(a) == root(c):
        loop += 1
    else:
        unite(a, c)

roots = list(i for i in range(N) if i == root(i))  # 内包表記でフィルタリング

print(loop, len(roots) - loop)

考え方2

連結かどうかをUnionFind木で管理する（UnionFind木 - 競プロはじめました）．
各ロープについて，両端を使ったかどうかを管理するflagを設ける．

連結成分の全てのロープの両端を使っていればループになっている．

from collections import defaultdict

N, M = map(int, input().split())
# --- UnionFind ---
p = [-1] * (N + 1)
def root(x):
    if p[x] < 0:
        return x
    p[x] = root(p[x])
    return p[x]
 
def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    p[x] += p[y]
    p[y] = x

def size(x):
    x = root(x)
    return -p[x]
# --- UnionFind ---

flag = [[False] * 2 for _ in range(N)]
for _ in range(M):
    a, b, c, d = input().split()
    a = int(a) - 1
    c = int(c) - 1
    unite(a, c)
    if b == 'R':
        flag[a][0] = True
    else:
        flag[a][1] = True
    if d == 'R':
        flag[c][0] = True
    else:
        flag[c][1] = True

d = defaultdict(list)
for i in range(N):
    d[root(i)].append(i)

loop = 0
for k in d:
    for i in d[k]:
        if not(flag[i][0] & flag[i][1]):break
    else:
        loop += 1

print(loop, len(d) - loop)