백준 10451 순열 사이클(DFS, Union-Find)

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

10451번: 순열 사이클

주어진 순열에 대해서 그래프를 만들고 그 그래프(사이클)이 몇개 있는지 파악하는 문제이다.

문제를 읽고 dfs,bfs나 union-find로 풀 수 있을 것 같다는 생각을 하여 풀었다.

 

union-find로 풀면서 헷갈리는 부분이 있었는데 이 알고리즘을 정확히 알아야한다.

union은 단순히 합치기, find는 부모노드를 찾는게 아닌 root노드를 찾는 것

 

즉, union을 한다음에 find을 해줘야 정확한 root노드를 찾는 것

단순히 union을 한다음 parent list로 판단해서는 잘못된 생각이다.

 

<DFS>

def dfs(v):
    if visited[v]:
        return 0
    visited[v] = 1
    for i in graph[v]:
        if not visited[i]:
            dfs(i)
    return 1

for _ in range(int(input())):
    n = int(input())
    data = list(map(int,input().split()))
    std = range(1,n+1)
    graph = [[] for _ in range(n+1)]
    visited = [0] * (n+1)

    cnt = 0
    for i in range(n):
        graph[std[i]].append(data[i])

    for i in range(1,n+1):
        cnt += dfs(i)
    print(cnt)

<Union-Find>

def find(target):
    if parent[target] != target:
        parent[target] = find(parent[target])
    return parent[target]

def union(a, b):
    global ans
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    elif a > b:
        parent[a] = b


for _ in range(int(input())):
    n = int(input())
    data = list(map(int,input().split()))
    parent = list(range(n+1))
    res = []

    for i in range(n):
        union(i+1,data[i])

    for i in range(n+1):
        res.append(find(i))
    print(len(list(set(res[1:]))))