23.04.20 Today’s Leetcode

662. Maximum Width of Binary Tree (medium)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        q = deque([(root, 1)])
        res = 0
        while q:
            temp = deque([])
            min_, max_ = math.inf, 0
            # print(q)
            while q:
                node, index = q.popleft()
                min_ = min(min_, index)
                max_ = max(max_, index)
                if node.left:
                    temp.append((node.left, index * 2))
                if node.right:
                    temp.append((node.right, index * 2 + 1))
            res = max(res, max_ - min_ + 1)
            q = temp
        
        return res

2608. Shortest Cycle in a Graph (hard)

test failed at 55/80

class Solution:
    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:
        visited = [-1] * n
        tree = defaultdict(list)
        for a, b in edges:
            tree[a].append(b)
            tree[b].append(a)

        def bfs(cur, count=0):
            q = deque([cur])
            while q:
                # print(q)
                temp = deque([])
                while q:
                    v = q.popleft()
                    visited[v] = count
                    for node in tree[v]:
                        if visited[node] >= 0:
                            if count - visited[node] <= 1:
                                continue
                            if count >= visited[node] and count + visited[node] >= 2:
                                return count + visited[node] + 1
                        else:
                            temp.append(node)
                
                q = temp
                count += 1

            return -1
        
        res = math.inf
        for i in range(n):
            if visited[i] == -1:
                d = bfs(i)
                if d > 0:
                    res = min(res, d)
        return -1 if res == math.inf else res
                

class Solution:
    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:
        G = [[] for _ in range(n)]
        for i, j in edges:
            G[i].append(j)
            G[j].append(i)
            
        def root(i):
            dis = [inf] * n
            dis[i] = 0
            bfs = [i]
            for i in bfs:
                for j in G[i]:
                    if dis[j] == inf:
                        dis[j] = 1 + dis[i]
                        bfs.append(j)
                    elif dis[i] <= dis[j]:
                        return dis[i] + dis[j] + 1
            return inf
        res = min(map(root, range(n)))
        return res if res < inf else -1

class Solution:
    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:
        adj = [[] for _ in range(n)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)
        covered, parent = {}, [-1]*n
        res = INF = float("inf")
        for x in range(n):
            if x in covered:
                continue
            queue = deque([x])
            covered[x] = 0
            while len(queue) > 0:
                y = queue.popleft()
                for z in adj[y]:
                    if parent[y] == z:
                        continue
                    if z in covered:
                        a, b = y, z
                        while a != b:
                            if covered[a] >= covered[b]:
                                a = parent[a]
                            else:
                                b = parent[b]
                        res = min(res, covered[y] + covered[z] + 1 - 2 * covered[a])
                    else:
                        parent[z] = y
                        covered[z] = covered[y] + 1
                        queue.append(z)
        return res if res != INF else -1