AtCoder Beginner Contest 204 C - Tour

BFS

N,M=map(int,input().split())
ab=[]
for i in range(M):
    tmp=list(map(int,input().split()))
    ab.append(tmp)


from collections import defaultdict,deque

graph=defaultdict(list)

for i in range(M):
    l=ab[i][0]
    r=ab[i][1]
    graph[l].append(r)
    #graph[r].append(l)



que=deque()


def BFS(x):
    S=set()
    que.append(x)
    S.add(x)
    
    while que:
        v=que.popleft()
        for i in graph[v]:
            if not i in S:
                que.append(i)
                S.add(i)
    return S

ans=0
for i in range(1,N+1):
    tmp=len(BFS(i))
    ans+=tmp

print(ans)

DFS

N,M=map(int,input().split())
ab=[]
for i in range(M):
    tmp=list(map(int,input().split()))
    ab.append(tmp)


graph=[[] for i in range(N)]

for i in range(M):
    a=ab[i][0]
    b=ab[i][1]
    graph[a-1].append(b-1)

def DFS(x):
    if temp[x]:
        return
    temp[x]=True
    for v in graph[x]:
        DFS(v)

ans=0

for i in range(N):
    temp=[False]*N
    DFS(i)
    ans+=sum(temp)


print(ans)