终于开始写技术博客啦，之前一直想要尝试但是由于太懒，刷题的顺序比较随意，刷题之后也没有总结，现在终于开始认真的按照Tag刷题啦，所以开始写第一篇技术博客啦: )
首先把题目抄一下:
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.
Example1:
Input: n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true
Example2:
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.
这个题目被Leetcode划分到了Union-Find, Graph, BFS,以及DFS这几个标签下，我是在Graph的标签底下刷到的。
题目分析与转化
那么首先来分析一波，其实这个题目作为一个图的题目来看，因为返回的是bool型数据，那吗判断结果为true的等价条件是
(1)边数=n-1
(2)连通分支的数量为1
(3)连通分支内没有环(1)边数=n-1
(2)连通分支数量为1
这两个都是等价条件，但显然第1个条件更复杂，多了一个条件。这是为啥，因为1中的(3)其实可以从(1)(2)推出。(3)其实是冗余的。
具体实现思路
1. DFS
首先图的题目我是比较偏向于dfs的，那么第一版本的我的代码就是用dfs实现的，而且我选的等价条件是第1个，其实有点绕。
1.1 等价条件1
class Solution {
public:
bool dfs(int i,int pre,vector<bool>& visited ,vector<vector<int>>& graph){
if(visited[i])return false;
visited[i]=true;
for(auto child: graph[i]){
if(child!=pre){
if(!dfs(child, i, visited, graph))return false;
}
}
return true;
}
bool validTree(int n, vector<vector<int>>& edges) {
if(edges.size()!=n-1)return false;
vector<bool> visited(n,false);
vector<vector<int>> graph(n,vector<int>());
for(auto vec: edges){
graph[vec[0]].push_back(vec[1]);
graph[vec[1]].push_back(vec[0]);
}
if(dfs(0,-1, visited, graph)==false)return false;
for(auto i:visited){
if(i==false)return false;
}
return true;
}
};
因为我用的等价条件1，所以还要涉及处理无向图中是否有环的问题（这其实没必要而且挺麻烦的，但是我一开始没有想到最简洁的等价转化方法）。
那么连通的无向图，无环则是树，有环则在dfs过程中出现重复访问的节点，需要注意的是，因为是无向图，所以dfs的时候需要把父节点排除筛查范围。
1.2 等价条件2
class Solution {
public:
void dfs(int i,vector<bool>& visited ,vector<vector<int>>& graph){
if(visited[i])return;
visited[i]=true;
for(auto child: graph[i]){
dfs(child, visited, graph);
}
}
bool validTree(int n, vector<vector<int>>& edges) {
if(edges.size()!=n-1)return false;
vector<bool> visited(n,false);
vector<vector<int>> graph(n,vector<int>());
for(auto vec: edges){
graph[vec[0]].push_back(vec[1]);
graph[vec[1]].push_back(vec[0]);
}
dfs(0,visited, graph);
for(auto i:visited){
if(i==false)return false;
}
return true;
}
};
从代码中可以看出仅仅在dfs函数中有细微的差别。条件1更加简介，只是遍历连通分支，并不在意是否有环。
2. Union_Find
这个方法以为我一开始转化的时候转化的繁了所以并没有想到，但是这个方法其实非常直观。本来union_find就常用来判断连通分支数目。
class UnionFind{
vector<int> vec;
int count;
public: UnionFind(int n){
vec= vector<int>(n,0);
for(int i=0;i<n;i++){
vec[i]=i;
}
count=n;
}
public: void union_(int a, int b){
int RA = find(a);
int RB = find(b);
if(RA==RB)return;
else {
vec[RA]=RB;
count--;
}
}
public: int find(int a){
while(vec[a]!=a){
vec[a]=vec[vec[a]];
a=vec[a];
}
return a;
}
public: int getCount(){
return count;
}
};
class Solution {
public:
bool validTree(int n, vector<vector<int>>& edges) {
if(edges.size()!=n-1)return false;
UnionFind uf(n);
for(auto edge:edges){
uf.union_(edge[0], edge[1]);
}
return uf.getCount()==1;
}
};
union-find的时候要注意，为了减少时间复杂度，可以选择在find的时候减少树的高度。
OKK完结撒花！
