首先需要建立一个adjacency Matrix. A list of List. 表示每个vertex 能够到的vertex。

判断一个Graph是不是Tree 主要的条件是 1. 不能有cycle   2. 所有node都connected。

DFS+Adjacency Matrix.

一个很容易错的地方在因为这是一个undirected graph, 所以edge是双向的。添加入Adjacency 时候很容易只加了单方向的edge。

最难的地方在于如何check Cycle. 虽然是用DFS做， 但是跟普通DFS遍历tree还是有点不一样。首先你也不知道他是不是tree，也许并没有connected。所以即便到了某一个node，然后这个node从来没去过，也不能就得出结论说这里很ok之类的。因为如果这个node的parent 就说他自己的话，那还是一个cycle！ 还有就是用一个visited 的array来表示有没有去过一个地方也是非常重要的。

UnionFind

Union Find使用的时候要assume node没有self loop。还是老套路，用一个parent array. 

For each edge, make subset using both vertices. If both vertices are in the same subset, found a cycle.

蛮deep的概念，看底下的英文解释会比较容易理解。