Today's Challenge

fabichoi 2023. 1. 15. 23:45

https://leetcode.com/problems/number-of-good-paths/

Number of Good Paths - LeetCode

Number of Good Paths - There is a tree (i.e. a connected, undirected graph with no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. You are given a 0-indexed integer array vals of length n where vals[i] denotes the value of t

leetcode.com

길찾기 관련 문제가 계속 나오네 ㅠ_ㅠ
오늘도 무지성 솔루션 복붙 ㅠ_ㅠ

class Solution:
    def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
        n = len(vals)
        p = list(range(n))
        count = [Counter({vals[i]:1}) for i in range(n)] 
        edges = sorted((max(vals[i], vals[j]), i, j) for i, j in edges)
        res = n

        def find(i):
            if p[i] != i:
                p[i] = find(p[i])
            return p[i]

        for val, i, j in edges:
            pi, pj = find(i), find(j)
            res += count[pi][val] * count[pj][val]
            p[pi] = pj
            count[pj][val] += count[pi][val]
        
        return res