ABC292D - Unicyclic Components

考え方

UnionFind木（UnionFind木 - 競プロはじめました）で辺で結ばれる頂点をマージする．辺の数は，UnionFind木の親に対応付けて管理する．

回答例

N, M = map(int, input().split())
E = []
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    E.append((u, v))

# --- 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 ---
cnt = [0] * N
for u, v in E:
    unite(u, v)
    cnt[u] += 1

num = [0] * N
for i in range(N):
    num[root(i)] += cnt[i]

for i in range(N):
    if num[root(i)] != size(i):
        exit(print('No'))
print('Yes')