261. Graph Valid Tree

題目網址：https://leetcode.cn/problems/graph-valid-tree/

題意：給定編號 0 到 n - 1 的 n 個 node, 和一個無向邊的 list edges, 其中 edges[i] = [a, b] 代表 graph 中 a 和 b 之間有一邊, 返回此 graph 是否為 tree。

注意：edges 中沒有重複的邊（e.g. [1, 0] 和 [0, 1] 不會同時出現在 edges 中）

Solution 1：

想法：利用 DFS, 若 graph 要為 tree, 則必須滿足以下兩點：

• graph 中不可有 cycle
• graph 必須為 connected, 也就是圖中任兩點必定有邊相連, 不能有 isolated vertex

class Solution {
public:
    bool validTree(int n, vector<vector<int>> &edges) {
        vector<vector<int>> adj(n); // adjacent list
        vector<bool> visited(n, false);

        // build graph
        for (const auto& e : edges) {
            adj[e[0]].emplace_back(e[1]);
            adj[e[1]].emplace_back(e[0]);
        }
        // dfs 起始點為 0, 令 0 的前一個 node 設為 -1
        return dfs(adj, visited, 0, -1) && connected(visited);
    }

private:
    // 若無 cycle, 則 dfs 會 return true; 否則 return false
    bool dfs(vector<vector<int>>& adj, vector<bool>& visited, int cur, int prev){
        // 若有 node 被重複拜訪, 代表有 cycle
        if (visited[cur]) {
            return false;
        }

        visited[cur] = true; // 將 cur 設為已拜訪

        for (const auto& v : adj[cur]) { // dfs 拜訪 adjacent node
            // 若 v 為前一個 node, 則不進行 dfs
            if (v != prev) {
                if (!dfs(adj, visited, v, cur)) {
                    return false; // 若有 cycle
                }
            }
        }

        return true;
    }

    // 判斷圖中所有點是否都有被拜訪到
    bool connected(vector<bool>& visited){
        for (const auto& v : visited) {
            if (!v) {
                return false; // 若有點沒被拜訪到
            }
        }
        return true;
    }
};

• time：$O(V + E)$ ➔ 必須拜訪所有 node, 和其延伸出去的所有 edge
  • V 是 node 數, E 是 edge 數
• space：$O(V + E)$ ➔ 因為 adj 為 $O(V + E)$, V 是因為要記錄所有點, E 是因為會記錄所有邊

Solution 2：

想法：利用 BFS

class Solution {
public:
    bool validTree(int n, vector<vector<int>> &edges) {
        // build graph
        vector<unordered_set<int>> adj(n);
        for (const auto& e : edges) {
            adj[e[0]].emplace(e[1]);
            adj[e[1]].emplace(e[0]);
        }

        queue<int> q({0}); // 初始點設為 0
        unordered_set<int> visited({0}); // 初始點設為 0

        while (!q.empty()) {
            for (int k = q.size(); k > 0; --k) {
                const auto cur = q.front();
                q.pop();

                for (const auto& v : adj[cur]) {
                    // 若 v 已被拜訪代表有 cycle, 返回 false
                    if (visited.find(v) != visited.end()) {
                        return false;
                    }

                    visited.emplace(v);
                    q.emplace(v);
                    adj[v].erase(cur); // 避免等下拜訪 v 時重複拜訪 cur
                }
            }
        }
        return visited.size() == n; // 判斷是否所有點都被拜訪到
    }
};

• time：$O(V + E)$ ➔ 必須拜訪所有 node, 和其延伸出去的所有 edge
  • V 是 node 數, E 是 edge 數
• space：$O(V + E)$ ➔ adj

Solution 3：

想法：利用 Union Find + Path Compression, 用 Union Find 合併每條邊的兩個 node 時, 如果這兩個 node 已經在同一 set 中, 則存在 cycle

e.g. edges = [[1,2], [1, 3], [2, 3]]

• 當完成 [1, 2] 和 [1, 3] 時, parents[2] = 1 = parents[3]
• 然後執行 [2, 3] 時, 因為 parents[2] == parents[3] 代表有 cycle

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        vector<int> parents(n, 0); // 紀錄每個點的 parent
        vector<int> ranks(n, 1); // 紀錄每個點的 rank

        // 每個點的 parent 都初始成自己
        for (int i = 0; i < n; ++i) {
            parents[i] = i;
        }

        res = n; // 一開始令每個 node 都自己一個 set, 然後才開始合併
        for (const auto& e : edges) {
            const int r1 = find(parents, e[0]); // root of a
            const int r2 = find(parents, e[1]); // root of b

            // a, b 已經是同個 set, 則代表加入 e 後會形成 cycle
            if (r1 == r2) {
                return false;
            }

            // a, b 是不同 set, 則兩個 set 合併成一個 set
            union_(parents, ranks, r1, r2);
        }
        return res == 1; // 合併到最後只剩下一個 set, 代表所有 node 皆 connected
    }

private:
    int res;

    void union_(vector<int>& parents, vector<int>& ranks, const int r1, const int r2){
        if (ranks[r1] > ranks[r2]) {
            parents[r2] = r1;
        } else if (ranks[r2] > ranks[r1]) {
            parents[r1] = r2;
        } else {
            parents[r2] = r1;
            ranks[r1]++;
        }
        --res; // 合併後, set 數 - 1
    }

    int find(vector<int>& parents, int i){
        while (i != parents[i]) {
            parents[i] = parents[parents[i]]; // path compression
            i = parents[i];
        }
        return i;
    }
};

• time：$O(V + E)$ ➔ 遍歷每個 node 初始化 parents, 以及遍歷每條 edge 做 union find, 其中 edge 的兩端點做 find() 皆只需 $O(1)$
• space：$O(n)$ ➔ parents, ranks