[LeetCode] Graph Valid Tree

朱雀 2021-12-03 07:17 114阅读 0赞

**[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.

For example:

Given `n = 5` and `edges = [[0, 1], [0, 2], [0, 3], [1, 4]]`, return `true`.

Given `n = 5` and `edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]`, return `false`.

Hint:

1.  Given `n = 5` and `edges = [[0, 1], [1, 2], [3, 4]]`, what should your return? Is this case a valid tree?
2.  According to the [definition of tree on Wikipedia][]: “a tree is an undirected graph in which any two vertices are connected by *exactly* one path. In other words, any connected graph without simple cycles is a tree.”

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

首先要判断是不是只有一个连通分支，如果不是肯定不是树，如果只有一个连通分支，再判断分支内有没有环，如果没有环，那么就是树。求连通分支个数用并查集，判断是否有环用DFS。

1 class Solution {
     2 public:
     3     int findFather(vector<int> &father, int x) {
     4         while (x != father[x]) x = father[x];
     5         return x;
     6     }
     7     bool dfs(vector<vector<int>> &graph, vector<bool> &visit, int u, int f) {
     8         visit[u] = true;
     9         for (auto v : graph[u]) if (v != f) {
    10             if (visit[v]) return false;
    11             else if (!dfs(graph, visit, v, u)) return false;
    12         }
    13         return true;
    14     }
    15     bool validTree(int n, vector<pair<int, int>>& edges) {
    16         vector<int> father(n);
    17         for (int i = 0; i < n; ++i) father[i] = i;
    18         for (auto edge : edges) {
    19             int fa = findFather(father, edge.first), fb = findFather(father, edge.second);
    20             if (fa < fb) father[fb] = fa;
    21             else father[fa] = fb;
    22         };
    23         int cnt = 0;
    24         for (int i = 0; i < n; ++i) {
    25             if (i == father[i]) ++cnt;
    26             if (cnt > 1) return false;
    27         }
    28         vector<vector<int>> graph(n);
    29         vector<bool> visit(n, false);
    30         for (auto edge : edges) {
    31             int u = edge.first, v = edge.second;
    32             graph[u].push_back(v);
    33             graph[v].push_back(u);
    34         }
    35         return dfs(graph, visit, 0, -1);
    36     }
    37 };

转载于:https://www.cnblogs.com/easonliu/p/4784964.html

[Graph Valid Tree]: https://leetcode.com/problems/graph-valid-tree/
[definition of tree on Wikipedia]: https://en.wikipedia.org/wiki/Tree_%28graph_theory%29