Submission #2696721

---

Source Code Expand

from collections import defaultdict

n, m = map(int, input().split())

graph = defaultdict(list)
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

visited = set()

def dfs(v):
    stack = [(None, v)]
    while stack:
        last, current = stack.pop()
        if current in visited:
            return 0
        visited.add(current)
        stack.extend((current, node) for node in graph[current] if node != last)
    return 1

ans = 0
for node in range(1, n+1):
    if node not in visited:
        ans += dfs(node)

print(ans)

Submission Info

Judge Result