LeetCode-Python-261. 以图判树

56 阅读 0 评论 37 点赞

我是靠谱客的博主忧郁自行车，最近开发中收集的这篇文章主要介绍LeetCode-Python-261. 以图判树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给定从 0 到 n-1 标号的 n 个结点，和一个无向边列表（每条边以结点对来表示），请编写一个函数用来判断这些边是否能够形成一个合法有效的树结构。

示例 1：

输入: n = 5, 边列表 edges = [[0,1], [0,2], [0,3], [1,4]]
输出: true
示例 2:

输入: n = 5, 边列表 edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
输出: false
注意：你可以假定边列表 edges 中不会出现重复的边。由于所有的边是无向边，边 [0,1] 和边 [1,0] 是相同的，因此不会同时出现在边列表 edges 中。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/graph-valid-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

首先要知道树的定义：

我个人的理解简单讲就是，一个图，如果从图里的某个节点出发，可以到达所有的结点，而且图里没有环，那么这个图就可以被称为树。

所以对于这道题，我们需要判断两个东西：

1. 是不是只有一个根结点（等同于找有几个帮派老大）

2. 图里有没有环

第一个问题是非常典型的并查集应用，所以本题用并查集解题。

开个并查集，在把所有的边丢进并查集之前，判断一下它们的老大相不相同，

如果已经相同了，那么丢进去之后就说明会形成环。

如果图里不存在环，那么最后判断一下有几个根结点即可。

class UnionFindSet(object):
def __init__(self, n):
self.count = n
self.roots = [i for i in range(n)]
def find(self, node):
while self.roots[node] != node:
node = self.roots[node]
return node
def union(self, p, q):
p_parent = self.find(p)
q_parent = self.find(q)
self.roots[p_parent] = q_parent
self.count -= 1
class Solution(object):
def validTree(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: bool
"""
#开并查集，如果一条边的两个顶点在放进图之前就有相同的根结点，则说明这条边放进去之后会形成一个环
ufs = UnionFindSet(n)
for start, end in edges:
if ufs.find(start) == ufs.find(end):
return False
ufs.union(start, end)
# print ufs.count
return ufs.count == 1