Submission #3404716

---

Source Code Expand

import sys
sys.setrecursionlimit(250000)

# input
N, M = (int(i) for i in input().split())
u = []
v = []
tf = [False for i in range(N + 1)]
for m in range(M):
    u_, v_ = (int(i) for i in input().split())
    u.append(u_)
    v.append(v_)

def dfs(i):
    isTree = False
    tf[u[i]] = True
    tf[v[i]] = True
    for j in range(i + 1, M):
        if tf[u[j]] and tf[v[j]]:
            isTree = False
        if v[i] == u[j] and tf[v[j]] == False:
            tf[v[j]] = True
            dfs(i+1)
            isTree = True
    return 1 if isTree else 0

ans = 0
for i in range(M):
    # already checked
    if tf[u[i]] and tf[v[i]]:
        continue
    ans += dfs(i)

for i in range(1, N + 1):
    if not tf[i]:
        ans += 1
if M == 1:
    ans += 1
print(ans)

Submission Info

Judge Result