Will the Guru

Graph Valid Tree

Published by

youngkih21

on

October 3, 2024

Problem

https://leetcode.com/problems/graph-valid-tree/description/

Solution #1. DFS

class Solution {
    private int n;
    private boolean[][] paths;
    private boolean result;
    public boolean validTree(int n, int[][] edges) {
        this.n = n;
        this.paths = new boolean[n][n];
        this.result = false;

        for (int i=0;i<edges.length;i++) {
            int start = edges[i][0];
            int end = edges[i][1];
            
            paths[start][end] = true;
            paths[end][start] = true;
        }

        Set<Integer> visited = new HashSet<>();
        visited.add(0);
        solve(0, visited);

        return result;
    }

    private void solve(int node, Set<Integer> visited) {
        if (visited.size() == n) {
            result = true;
            return;
        }

        for (int i=0;i<n;i++) {
            if (paths[node][i]) {
                if (visited.contains(i)) {
                    result = false;
                    return;
                }
                
                visited.add(i);
                paths[i][node] = false;
                solve(i, visited);
                paths[i][node] = true;
            }
        }
    }
}

DFS 으로 풀이
- 이 때, undirected path 이므로, A <-> B 를 cycle 로 인식하지 않도록 하기 위해 path 를 통과하면 반대방향 path 는 없는것처럼 제거

Solution #2. Union-Find

// 1. 우선 edges 숫자가 n-1 이여야 valid graph  
// 2. edges 들을 돌면서 union(x, y) 진행. 
// 3. 모든 vertex 의 root 가 전부 동일해야 valid graph
class Solution {
    private int[] rootArray;
    public boolean validTree(int n, int[][] edges) {
        // KEY POINT #1.
        if (edges.length != n-1) {
            return false;
        }

        this.rootArray = new int[n];
        for (int i=0;i<n;i++) {
            rootArray[i] = i;
        }

        for (int i=0;i<edges.length;i++) {
            int x = edges[i][0];
            int y = edges[i][1];

            union(x, y);
        }

        for (int i=0;i<n-1;i++) {
            if (find(i) != find(i+1)) { // KEY POINT #2.
                return false;
            }
        }
        return true;
    }

    private void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            rootArray[rootY] = rootX;
        }
    }

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

        rootArray[x] = find(rootArray[x]);
        return rootArray[x];
    }
}

KEY POINT
- #1. 유효한 graph 려면, vertex 수가 n 이라면 edge 수는 n-1 이여야 한다!
- #2. 유효한 graph 려면, 모든 vertex 의 root 가 동일해야한다!
  - 즉, find() 결과가 전부 동일해야한다!

Solution #3. Union-Find with boolean type

// 1. 우선 edges 숫자가 n-1 이여야 valid graph  
// 2. edges 들을 돌면서 union(x, y) 진행. 
// 3. rootArray 내 root 가 전부 동일해야 valid graph
class Solution {
    private int[] rootArray;
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n-1) {
            return false;
        }

        this.rootArray = new int[n];
        for (int i=0;i<n;i++) {
            rootArray[i] = i;
        }

        for (int i=0;i<edges.length;i++) {
            int x = edges[i][0];
            int y = edges[i][1];

            if(hasCycle(x, y)) {
                return false;
            }
        }

        return true;
    }

    private boolean hasCycle(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) {
            return true;
        } 

        rootArray[rootY] = rootX;
        return false;
    }

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

        rootArray[x] = find(rootArray[x]);
        return rootArray[x];
    }
}

hasCycle() 이 union() 와 동일한 메소드
- union(x, y) 할 때, x 와 y 가 동일한 root vertex 를 가지고 있다면, 이는 같은 군에 있다는 의미.
  => 즉, 이미 그룹에 추가가 되어 있다는 뜻.
  => 이미 그룹에 추가가 되어있는데 union(x, y)이 불렸다는 건 cycle 이 있다는 뜻이다!!

Leave a comment Cancel reply