[Swift]LeetCode261.图验证树 $ Graph Valid 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.

给定n个标记为0到n-1的节点和一个无向边列表（每个边都是一对节点），编写一个函数来检查这些边是否构成有效的树。

例如：

如果n=5且边数为[[0，1]，[0，2]，[0，3]，[1，4]]，则返回true。

如果n=5且边数为[[0，1]，[1，2]，[2，3]，[1，3]，[1，4]]，则返回false。

提示：

考虑到n=5和edges=[[0，1]，[1，2]，[3，4]]，你应该返回什么？这是一个有效的树吗？

根据维基百科上树的定义：“树是一个无向图，其中任何两个顶点都由一条路径连接。换句话说，任何没有简单循环的连通图都是一棵树。”

注意：可以假定边中不会出现重复的边。因为所有边都是无向的，[0，1]与[1，0]相同，因此不会在边中一起出现。

 BFS 

 1 class Solution { 2     func valIDTree(_ n:Int,_ edges:[[Int]]) -> Bool{ 3         var g:[Set<Int>] = [Set<Int>](repeating:Set<Int>(),count:n) 4         var s:Set<Int> = [0] 5         var q:[Int] = [0] 6         for a in edges 7         { 8             g[a[0]].insert(a[1]); 9             g[a[1]].insert(a[0]);10         }11         while(!q.isEmpty)12         {13             var t:Int = q.first!14             q.removeFirst()15             for a in g[t]16             {17                 if s.contains(a)18                 {19                     return false20                 }21                 s.insert(a)22                 q.append(a)23                 g[a].remove(t)24             }25         }26          return s.count == n27     }28 }

以上是内存溢出为你收集整理的[Swift]LeetCode261.图验证树 $ Graph Valid Tree全部内容，希望文章能够帮你解决[Swift]LeetCode261.图验证树 $ Graph Valid Tree所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。