LeetCode--以图判树（Python）_判断一个图是否是树python

LeetCode–以图判树（Python）

题目描述

给定从 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

从一个图里的某个节点出发,判断是否只有一个根节点,并且判断是否有没有闭环.

class FindSet(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):
        pparent = self.find(p)
        qparent = self.find(q)
        self.roots[pparent] = qparent
        self.count -= 1
        
class Solution(object):
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        fs = FindSet(n)
        for start, end in edges:
            if fs.find(start) == fs.find(end):
                return False
            fs.union(start, end)
            
        return ufs.count == 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31