sashuIya

#!/bin/python3

import math
import os
import random
import re
import sys

from collections import defaultdict

sashuIya

class Node:
    def __init__(self, k, v):
        self.key = k
        self.value = v
        self.next = None
        self.prev = None


class List:
    def __init__(self):

sashuIya

def dfs(v, edges, color, visited, colors):
    colors[v] = color
    visited.add(v)

    for u in edges[v]:
        if u in visited: continue
        dfs(u, edges, (color + 1) % 2, visited, colors)


class Solution:

sashuIya

class Solution:
    def merge_0(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        current_start = intervals[0][0]
        current_end = intervals[0][1]
        res = []
        for a, b in intervals:
            if a <= current_end:
                # current_start, a, current_end, b; OR
                # current_start, a, b, current_end

sashuIya

def bruteforce(i, s, balance, res):
    if i == len(s):
        res.append(''.join(s))
        return
    
    if balance > 0:
        s[i] = ')'
        bruteforce(i + 1, s, balance - 1, res)

    s[i] = '('

sashuIya

class TrieNode:
    def __init__(self):
        self.is_terminated = False
        self.links = dict()

def dfs(p, word, index):
    if index == len(word):
        return p.is_terminated 

    if word[index] == '.':

sashuIya

# https://leetcode.com/problems/clone-graph/

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

sashuIya

# https://leetcode.com/problems/house-robber-iii/description/

# 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

def dfs(v, can_rob: bool, res):

sashuIya

# https://leetcode.com/problems/number-of-provinces

def dfs(v, isConnected, used):
    used[v] = True

    for u, w in enumerate(isConnected[v]):
        if w == 1 and not used[u]:
            dfs(u, isConnected, used)

sashuIya

# https://leetcode.com/problems/path-with-minimum-effort/description/

dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs(v, m, heights, used):
    queue = deque([v])
    used.add(v)

    while queue:
        x, y = queue.popleft()