이문제 union & find로 풀수 있는데 이경우 dfs와 비교했을때 시간복잡도는 어떤 접근법이 나은가요?

8 asked

0

안녕하세요 ㅎㅎ

UF가 근소하게 빠릅니다. DFS는 O(N + M)이지만 UF는 O(아커만(N) + M)이며 아커만의 특성상 O(1)에 가깝기 때문에 O(M)이라고 볼 수 있기 때문에 더 빠르지만... 사실 거의 비슷하다고 봐도 무방합니다.

실제로 UF와 DFS 제출 코드를 비교했을 때의 걸린 시간은 똑같은 것을 볼 수 있습니다.

참고로 UF로 푼 C++ 코드는 다음과 같습니다.

#include <cstdio>
using namespace std;

int parent[1004];

int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void unionSet(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    if (pa != pb) parent[pb] = pa;
}

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        int n, m;
        scanf("%d %d", &n, &m);
        bool isTree = true;
        if(m != n - 1) {
            for(int i = 0; i < m; i++){
                int a, b;
                scanf("%d %d", &a, &b);
            }
            printf("graph\n");
            continue;
        }
        for(int i = 1; i <= n; i++){
            parent[i] = i;
        }
        for(int i = 0; i < m; i++){
            int a, b;
            scanf("%d %d", &a, &b);
            if(find(a) == find(b)) {
                isTree = false;
            } else {
                unionSet(a, b);
            }
        }
        if(isTree)
            printf("tree\n");
        else
            printf("graph\n");
    }
    return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

0

자바이긴 합니다...

package _4thweek;

import java.util.Scanner;

public class Baekjoon13244 {
    static int[] arr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        for (int tc = 0; tc < t; tc++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            boolean isTree = true;

            arr = new int[n + 1];

            if (m != n - 1) {
                isTree = false;
            }

            for (int i = 1; i <= n; i++) {
                arr[i] = i;
            }

            for (int i = 0; i < m; i++) {
                int parent = sc.nextInt();
                int child = sc.nextInt();

                if (!union(parent, child)) {
                    isTree = false;
                }
            }

            int root = find(1);
            for (int i = 1; i <= n; i++) {
                if (root != find(i)) {
                    isTree = false;
                    break;
                }
            }

            if (isTree) {
                System.out.println("tree");
            } else {
                System.out.println("graph");
            }
        }
    }

    static boolean union(int parent, int child) {
        int rootA = find(parent);
        int rootB = find(child);

        if (rootA == rootB) {
            return false;
        }
        arr[rootB] = rootA;
        return true;
    }

    static int find(int node) {
        if (arr[node] == node) {
            return node;
        }
        return arr[node] = find(arr[node]);
    }
}

0

안녕하세요 ㅎㅎ UF를 이용한 코드 공유 부탁드립니다.