261. Graph Valid Tree

Given n nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

Example 1:

Input: n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true

Example 2:

Input: n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: false

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0,1] is the same as [1,0]and thus will not appear together in edges.

最有效率的方法是union-find，根據edges來union節點，如果發現在union前兩節點就已經屬於同一個group，那麼當前這個edge就是多餘的edge，也就是這個tree已經有circle產生，這種情況直接return false。如果順利掃完全部edges，最後要檢查總edge數量和節點數量之間的關係是否合理。

// Union find
int getRoot(vector<int>& roots, int i) {
    return roots[i] == -1 ? i : roots[i] = getRoot(roots, roots[i]);
}
bool validTree(int n, vector<vector<int>>& edges) { // time: O(E + log*(n)); space: O(n)
    vector<int> roots(n, -1), size(n, 1);
    for (auto& edge : edges) {
        int r1 = getRoot(roots, edge[0]), r2 = getRoot(roots, edge[1]);
        if (r1 == r2) return false;
        if (size[r1] >= size[r2]) {
            roots[r2] = r1;
            size[r1] += size[r2];
        } else {
            roots[r1] = r2;
            size[r2] += size[r1];
        }
    }
    return edges.size() == n - 1;
}

利用2D vector來建立一個adjacency list，還有一個1D array來紀錄是否掃描過某節點，在進行DFS時保留上一個掃描的節點資訊，以避免重複一樣的節點。最後掃瞄完undirected graph後確認是否每個節點都被掃描過，如果有節點沒被掃到，那這個tree就不合理。

// DFS
bool dfs(vector<vector<int> >& graph, vector<bool>& visited, int cur, int pre) {
    if (visited[cur]) return false; // a circle occurs
    visited[cur] = true;
    for (int neighbor : graph[cur]) {
        if (neighbor != pre) {
            if (!dfs(graph, visited, neighbor, cur)) return false;
        }
    }
    return true;
}
bool validTree(int n, vector<vector<int>>& edges) { // time: O(E + n); space: O(E + n)
    vector<vector<int> > graph(n, vector<int>()); // adjacency list
    vector<bool> visited(n, false);
    for (vector<int>& edge : edges) {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }
    if (!dfs(graph, visited, 0, -1)) return false;
    // check whether every node is visited after dfs
    for (bool v : visited) {
        if (!v) return false;
    }
    return true;
}

BFS時掃瞄完要把節點移除，考量到vector的移除效率不是這麼好，所以選擇利用vector<unordered_set<int> >建立adjacency list。最後要檢查所有掃描過的節點數量是否符合題目給的n值。

// BFS
bool validTree(int n, vector<vector<int>>& edges) { // time: O(n + E); space: O(n + E)
    vector<unordered_set<int> > graph(n, unordered_set<int>()); // adjacency list
    for (vector<int>& edge : edges) {
        graph[edge[0]].insert(edge[1]);
        graph[edge[1]].insert(edge[0]);
    }
    unordered_set<int> visited({0});
    queue<int> q({0});
    while (!q.empty()) {
        int t = q.front(); q.pop();
        for (int neighbor : graph[t]) {
            if (visited.count(neighbor)) return false;
            visited.insert(neighbor);
            q.push(neighbor);
            graph[neighbor].erase(t);
        }
    }
    return visited.size() == n;
}

684. Redundant Connection