Skip to content

Instantly share code, notes, and snippets.

@maehrm

maehrm/abc229_e.py

Created March 12, 2026 11:03
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save maehrm/eb29c2b3f85695d46b24e5063adb1d6e to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save maehrm/eb29c2b3f85695d46b24e5063adb1d6e to your computer and use it in GitHub Desktop.
Download ZIP
Raw
abc229_e.py
from atcoder.dsu import DSU
N, M = map(int, input().split())
G = [[] * N for _ in range(N)]
for _ in range(M):
a, b = map(lambda x: int(x) - 1, input().split())
G[a].append(b)
dsu = DSU(N)
curr = 0
ans = []
for u in range(N - 1, -1, -1):
ans.append(str(curr))
curr += 1
for v in G[u]:
if dsu.same(u, v):
continue
dsu.merge(u, v)
curr -= 1
print("\n".join(ans[::-1]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment