DFS /BFS - 순환 그래프 수 찾기

백준 11724 

DFS로 풀어보았다. 

 

import sys

sys.setrecursionlimit(10**9)

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

graph = [[] for _ in range(N+1)]

path = [False] * (N+1)

x= 0

while x < M :

    a,b = map(int,sys.stdin.readline().split())

    graph[a].append(b)

    graph[b].append(a)

    x = x+1

def DFS(start_node) :

    path[start_node] = True

    for i in graph[start_node] :

        if path[i] == False :

            path[start_node] = True

            DFS(i)

cnt = 0

for i in range(1,N+1) :

    if path[i] == False :

        DFS(i)

        cnt = cnt +1

print(cnt)

 

핵심은, 다른것은 없고 인접리스트를 사용하여 메모리를 감소시켰다는 것. 

SYS.SETRECURSIONLIMIT를 설정하여 최대 재귀를 증가시켰다는 것 . 

 

 

백준 10451 

import collections

t = int(input())
queue = collections.deque()

def bfs(index):
    queue.append(index)
    while queue:
        cur = queue.popleft()
        visited[cur] = True
        if visited[graph[cur]] == False:
            visited[graph[cur]] = True
            queue.append(graph[cur])

for i in range(t):
    n = int(input())
    graph = [0]+list(map(int, input().split()))
    visited = [0 for _ in range(n+1)]
    count = 0
    for j in range(1, n+1):
        if visited[j] == False:
            bfs(j)
            count += 1
    print(count)

 

고의적으로, BFS를 활용해 보았다.

 

핵심은 1. GRAPH가 1~N으로 들어와 [0] + SYS.~~로 표현할 수 있다는 것 .

2. CYCLE을 방문할때, VISITIED는 FALSE인 경우에만 방문해야 빠르다는 것. 

 

 

# 입력은 파일의 끝에서 처리한다. 가 갑자기 생각났다.

while 1:
    try:
        ins=input()
    
        ans = fun(ins)
        if ans == -1:
            break;
        else:
            print(ans)
    except EOFError:
        break



try , except(exception) EOFERROR: 시 를 주의하자