# 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`.

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

```cpp
// 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;
}
```

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

```cpp
// 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;
}
```

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

```cpp
// 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;
}
```

{% content-ref url="/pages/-LbomgCp7crOQgAqaZ8V" %}
[684. Redundant Connection](/practice-of-algorithm-problems/graph/684.-redundant-connection.md)
{% endcontent-ref %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/graph/261.-graph-valid-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.