[백준 파이썬 11724번]연결 요소의 개수 구하기★DFS★edge 리스트★VER3.0

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

VERSION 3.0 ==>연습연습!

import sys
sys.setrecursionlimit(10000) #최대 재귀한도
N , M = map(int,sys.stdin.readline().split())

edge = [ [] for i in range(N+1)]
visited = [False] * (N+1)
for i in range(M):
    u, v = map(int, sys.stdin.readline().split())
    edge[u].append(v)
    edge[v].append(u)

def dfs(e):

    if not visited[e]:
        visited[e] = True
        for p in edge[e]:
            dfs(p)


count = 0
for j in range(1,N+1):

    if not visited[j]:
        dfs(j)

        count+=1
print(count)

#%%

VERSION 2.0

import sys

sys.setrecursionlimit(10000)

N , M  = map(int, sys.stdin.readline().split())

edge = [[] for i in range(N+1)]

visited = [False] * (N+1)
count = 0

for i in range(M):
    u,v = map(int, sys.stdin.readline().split())
    edge[u].append(v)
    edge[v].append(u)
# print(edge)

def dfs(v):

    for e in edge[v]:
        if not visited[e]:
            visited[e] = True
            dfs(e)

for v in range(1, N+1):
    if not visited[v]:

        dfs(v)


        count+=1

print(count)



#%%

VERSION 1.0

import sys
sys.setrecursionlimit(10000)



N, M = map(int, sys.stdin.readline().split())
adj = [[] for _ in range(N + 1)]
#N = 6 , M = 5
#adj(EDGE) = [ [] [] [] [] [] [] [] ]
visited = [False] * (N + 1)
#visted = [ False , False , False , False , False , False , False]
count = 0

for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    adj[u].append(v)

    adj[v].append(u)
    #u , v = 1 , 2
    #adj[1].append(2) ==> adj = [ [] [2] [] [] [] [] [] ]
    #adj[2].append(1) ==> adj = [ [] [2] [1] [] [] [] [] ]

    #u , v = 2 , 5
    #adj[2].append(5) ==> adj = [ [] [2] [1,5] [] [] [] [] ]
    #adj[5].append(2) ==> adj = [ [] [2] [1,5] [] [] [2] [] ]

    #u , v = 5 , 1
    #adj[5].append(1) ==> adj = [ [] [2] [1,5] [] [] [2,1] [] ]
    #adj[1].append(5) ==> adj = [ [] [2,5] [1,5] [] [] [2,1] [] ]

    #u , v = 3 , 4
    #adj[3].append(4) ==> adj = [ [] [2,5] [1,5] [4] [] [2,1] [] ]
    #adj[4].append(3) ==> adj = [ [] [2,5] [1,5] [4] [3] [2,1] [] ]

    #u , v = 4 , 6
    #adj[4].append(6) ==> adj = [ [] [2,5] [1,5] [4] [3,6] [2,1] [] ]
    #adj[6].append(4) ==> adj = [ [] [2,5] [1,5] [4] [3,6] [2,1] [4] ]

def dfs(v):
    visited[v] = True
    for e in adj[v]:
        #adj = [ [] [2,5] [1,5] [4] [3,6] [2,1] [4] ]

        if not visited[e]:
            dfs(e)
# #visited = [ False , False , False , False , False , False , False]
#
for j in range(1, N + 1):
    if not visited[j]: #visited 가 False일때 , visited = [False , True , True , False,
        dfs(j)

        #j = 1
        #dfs(1)
        #visited[1] = True
        # for e in adj[1]=[2,5] , e= 2 , 5

        #visited[2] = False ==> dfs(2) , visited[5] = False ==> dfs(5)
        #dfs(2)
        #visited[2] = True
        #for e in adj[2] = [1,5] , e = 1 , 5

        #if not visited[1]= True'''' visited[5] = False
        #dfs(5)
        #visited[5] =True
        #for e in adj[5] = [2 , 1] , e = 2 , 1:

        #if not visited[2] = True , visited[1] = True


        #visited = [False , True , True , False, False , True , False]

        #count+= 1


        #j = 2
        #visited[2] = True

        #j = 3

        #visited[3] = False

        #dfs(3)
        #visited[3] = True
        #for e in adj[3] = [4]
        
        #if not visited[4] = False
        
        #dfs(4)
        #visited[4] = True
        #for e in adj[4] = [3,6] , e= 3 ,6
        
        #if not visited[3] = True , visited[6] = False
        #dfs(6)
        #visited[6] =True
        #for e in adj[6] = 4
        
        #if not visited[4] = True
        
        #visited = [False , True , True, True , True, True, True]
        #count+=1 = 2

        #j = 4
        
        #visited[4] = True
        
        #j=5

        #visited[5] = True

        #j=6

        #visited[6] = True
        
        count += 1

print(count) # count = 2

1. 인접한 요소에 따른 리스트 생성

 

adj = [[] for _ in range(N + 1)] ==> 1부터 숫자가 있으므로, N+1 개 생성

visited = [False] * (N + 1)
#visted = [ False , False , False , False , False , False , False]
count = 0

 

2. 인접한 요소에 따른 리스트 생성

for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    adj[u].append(v)
    adj[v].append(u)

 

1번째 , u , v = 1 , 2
    #adj[1].append(2) ==> adj = [ [] [2] [] [] [] [] [] ]
    #adj[2].append(1) ==> adj = [ [] [2] [1] [] [] [] [] ]

2번째 ,u , v = 2 , 5
    #adj[2].append(5) ==> adj = [ [] [2] [1,5] [] [] [] [] ]
    #adj[5].append(2) ==> adj = [ [] [2] [1,5] [] [] [2] [] ]

3번째 , u , v = 5 , 1
    #adj[5].append(1) ==> adj = [ [] [2] [1,5] [] [] [2,1] [] ]
    #adj[1].append(5) ==> adj = [ [] [2,5] [1,5] [] [] [2,1] [] ]

4번째 , u , v = 3 , 4
    #adj[3].append(4) ==> adj = [ [] [2,5] [1,5] [4] [] [2,1] [] ]
    #adj[4].append(3) ==> adj = [ [] [2,5] [1,5] [4] [3] [2,1] [] ]

5번째 , u , v = 4 , 6
    #adj[4].append(6) ==> adj = [ [] [2,5] [1,5] [4] [3,6] [2,1] [] ]
    #adj[6].append(4) ==> adj = [ [] [2,5] [1,5] [4] [3,6] [2,1] [4] ]

==> 1번 요소는 2,5

==> 2번 요소는 1,5

==> 3번 요소는 4

==> 4번 요소는 3,6

==> 5번 요소는 2,1

==> 6번 요소는 4

 

 

3. DFS 선언 

def dfs(v):
    visited[v] = True
    for e in adj[v]:
        #adj = [ [] [2,5] [1,5] [4] [3,6] [2,1] [4] ] ==> adj[v]의 리스트 안에 있는 값이 2개일경우, e는 2개의 값을 받아 2번 실행하게 된다.

        if not visited[e]:
            dfs(e)

 

3. DFS 실행 ==> 재귀함수 실행

 

for j in range(1, N + 1):
    if not visited[j]: #visited 가 False일때
        dfs(j)

        #j = 1
        #dfs(1)
        #visited[1] = True
        # for e in adj[1]=[2,5] , e= 2 , 5

        #visited[2] = False ==> dfs(2) , ★visited[5] = False ==> dfs(5)
        #dfs(2)
        #visited[2] = True
        #for e in adj[2] = [1,5] , e = 1 , 5

        #if not visited[1]= True, visited[5] = False
        #dfs(5)
        #visited[5] =True
        #for e in adj[5] = [2 , 1] , e = 2 , 1:

        #if not visited[2] = True , visited[1] = True

 

 

★ visited[5] = False--> True


        #visited = [False , True , True , False, False , True , False]

        #count+= 1


        #j = 2
        #visited[2] = True

        #j = 3

        #visited[3] = False

        #dfs(3)
        #visited[3] = True
        #for e in adj[3] = [4]
        
        #if not visited[4] = False
        
        #dfs(4)
        #visited[4] = True
        #for e in adj[4] = [3,6] , e= 3 ,6
        
        #if not visited[3] = True , visited[6] = False
        #dfs(6)
        #visited[6] =True
        #for e in adj[6] = 4
        
        #if not visited[4] = True
        
        #visited = [False , True , True, True , True, True, True]
        #count+=1 = 2

        #j = 4
        
        #visited[4] = True
        
        #j=5

        #visited[5] = True

        #j=6

        #visited[6] = True