from collections import defaultdict, deque
 
class Graph:
    """隣接リストによるグラフ表現"""
    def __init__(self, directed=False):
        self.adj = defaultdict(list)
        self.directed = directed
 
    def add_edge(self, u, v, weight=None):
        if weight is not None:
            self.adj[u].append((v, weight))
            if not self.directed:
                self.adj[v].append((u, weight))
        else:
            self.adj[u].append(v)
            if not self.directed:
                self.adj[v].append(u)
 
    def remove_edge(self, u, v):
        self.adj[u] = [x for x in self.adj[u] if x != v]
        if not self.directed:
            self.adj[v] = [x for x in self.adj[v] if x != u]
 
    def vertices(self):
        verts = set()
        for u in self.adj:
            verts.add(u)
            for v in self.adj[u]:
                if isinstance(v, tuple):
                    verts.add(v[0])
                else:
                    verts.add(v)
        return verts
 
    def degree(self, v):
        """頂点 v の次数を返す"""
        return len(self.adj[v])
 
    def has_edge(self, u, v):
        """辺 (u, v) が存在するか"""
        return v in self.adj[u]
 
    def __repr__(self):
        return '\n'.join(f'{u}: {neighbors}' for u, neighbors in self.adj.items())
 
 
class AdjacencyMatrix:
    """隣接行列によるグラフ表現"""
    def __init__(self, n, directed=False):
        self.n = n
        self.directed = directed
        self.matrix = [[0] * n for _ in range(n)]
 
    def add_edge(self, u, v, weight=1):
        self.matrix[u][v] = weight
        if not self.directed:
            self.matrix[v][u] = weight
 
    def remove_edge(self, u, v):
        self.matrix[u][v] = 0
        if not self.directed:
            self.matrix[v][u] = 0
 
    def has_edge(self, u, v):
        return self.matrix[u][v] != 0
 
    def neighbors(self, u):
        return [v for v in range(self.n) if self.matrix[u][v] != 0]
 
    def degree(self, u):
        return sum(1 for v in range(self.n) if self.matrix[u][v] != 0)

class EdgeListGraph:
    """辺リストによるグラフ表現（Kruskal等で有用）"""
    def __init__(self, directed=False):
        self.edges = []
        self.directed = directed
 
    def add_edge(self, u, v, weight=1):
        self.edges.append((u, v, weight))
        if not self.directed:
            self.edges.append((v, u, weight))
 
    def vertices(self):
        verts = set()
        for u, v, _ in self.edges:
            verts.add(u)
            verts.add(v)
        return verts
 
    def neighbors(self, u):
        return [(v, w) for src, v, w in self.edges if src == u]

def bfs(graph: dict, start) -> list:
    """幅優先探索 - O(V + E)"""
    visited = set([start])
    queue = deque([start])
    order = []
 
    while queue:
        vertex = queue.popleft()
        order.append(vertex)
 
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
 
    return order
 
# 最短経路（重みなし）
def bfs_shortest_path(graph: dict, start, end) -> list:
    """BFS で最短経路を復元"""
    visited = {start}
    queue = deque([(start, [start])])
 
    while queue:
        vertex, path = queue.popleft()
        if vertex == end:
            return path
 
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
 
    return []  # 到達不可能
 
# 最短距離（メモリ効率版）
def bfs_shortest_distance(graph: dict, start) -> dict:
    """全頂点への最短距離を計算（メモリ効率版）"""
    dist = {start: 0}
    queue = deque([start])
 
    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if neighbor not in dist:
                dist[neighbor] = dist[vertex] + 1
                queue.append(neighbor)
 
    return dist
 
# 使用例
g = {0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 3], 3: [1, 2, 4], 4: [3]}
print(bfs(g, 0))                    # [0, 1, 2, 3, 4]
print(bfs_shortest_path(g, 0, 4))   # [0, 1, 3, 4]
print(bfs_shortest_distance(g, 0))  # {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}

def bfs_levels(graph: dict, start) -> list:
    """レベル（距離）ごとに頂点をグループ化"""
    visited = {start}
    queue = deque([start])
    levels = []
 
    while queue:
        level_size = len(queue)
        current_level = []
 
        for _ in range(level_size):
            vertex = queue.popleft()
            current_level.append(vertex)
 
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
 
        levels.append(current_level)
 
    return levels
 
print(bfs_levels(g, 0))  # [[0], [1, 2], [3], [4]]

def is_bipartite(graph: dict, vertices: set) -> tuple:
    """二部グラフ判定 - O(V + E)
    返り値: (二部グラフか, 2色の割当辞書)
    """
    color = {}
 
    for start in vertices:
        if start in color:
            continue
 
        # BFS で 2色塗り
        color[start] = 0
        queue = deque([start])
 
        while queue:
            v = queue.popleft()
            for neighbor in graph.get(v, []):
                if neighbor not in color:
                    color[neighbor] = 1 - color[v]
                    queue.append(neighbor)
                elif color[neighbor] == color[v]:
                    return False, {}
 
    return True, color
 
# 二部グラフの例（木は常に二部グラフ）
g_bipartite = {
    0: [1, 3],
    1: [0, 2],
    2: [1, 3],
    3: [0, 2],
}
result, coloring = is_bipartite(g_bipartite, {0, 1, 2, 3})
print(f"二部グラフ: {result}")  # True
print(f"色分け: {coloring}")    # {0: 0, 1: 1, 3: 1, 2: 0}
 
# 非二部グラフの例（奇数サイクル）
g_odd = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
result, _ = is_bipartite(g_odd, {0, 1, 2})
print(f"二部グラフ: {result}")  # False

def multi_source_bfs(graph: dict, sources: list) -> dict:
    """複数始点BFS - O(V + E)
    各頂点から最寄りのソースまでの距離を計算
    """
    dist = {}
    queue = deque()
 
    for s in sources:
        dist[s] = 0
        queue.append(s)
 
    while queue:
        v = queue.popleft()
        for neighbor in graph.get(v, []):
            if neighbor not in dist:
                dist[neighbor] = dist[v] + 1
                queue.append(neighbor)
 
    return dist
 
# 実務例: グリッド上で複数の施設から各セルへの最短距離
# ゲーム開発での「最寄りの敵/味方までの距離マップ」生成に使われる
grid_graph = {
    (0,0): [(0,1), (1,0)],
    (0,1): [(0,0), (0,2), (1,1)],
    (0,2): [(0,1), (1,2)],
    (1,0): [(0,0), (1,1), (2,0)],
    (1,1): [(1,0), (0,1), (1,2), (2,1)],
    (1,2): [(1,1), (0,2), (2,2)],
    (2,0): [(1,0), (2,1)],
    (2,1): [(2,0), (1,1), (2,2)],
    (2,2): [(2,1), (1,2)],
}
sources = [(0,0), (2,2)]
distances = multi_source_bfs(grid_graph, sources)
print(distances)
# {(0,0): 0, (2,2): 0, (0,1): 1, (1,0): 1, (2,1): 1, (1,2): 1,
#  (1,1): 2, (0,2): 2, (2,0): 2}

def bfs_01(graph: dict, start) -> dict:
    """0-1 BFS - O(V + E)
    graph: {u: [(v, weight), ...]}  weight は 0 or 1
    """
    dist = defaultdict(lambda: float('inf'))
    dist[start] = 0
    dq = deque([start])
 
    while dq:
        u = dq.popleft()
        for v, w in graph.get(u, []):
            new_dist = dist[u] + w
            if new_dist < dist[v]:
                dist[v] = new_dist
                if w == 0:
                    dq.appendleft(v)  # 重み0 → 先頭に追加
                else:
                    dq.append(v)      # 重み1 → 末尾に追加
 
    return dict(dist)
 
# 例: グリッドで壁の破壊コスト 1、通路の移動コスト 0
graph_01 = {
    'A': [('B', 0), ('C', 1)],
    'B': [('A', 0), ('D', 1)],
    'C': [('A', 1), ('D', 0)],
    'D': [('B', 1), ('C', 0)],
}
print(bfs_01(graph_01, 'A'))
# {'A': 0, 'B': 0, 'C': 1, 'D': 1}

def dfs_recursive(graph: dict, start, visited=None) -> list:
    """DFS 再帰版 - O(V + E)"""
    if visited is None:
        visited = set()
 
    visited.add(start)
    order = [start]
 
    for neighbor in graph[start]:
        if neighbor not in visited:
            order.extend(dfs_recursive(graph, neighbor, visited))
 
    return order
 
def dfs_iterative(graph: dict, start) -> list:
    """DFS 反復版（スタック使用）"""
    visited = set()
    stack = [start]
    order = []
 
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            order.append(vertex)
            # 逆順に積むと辞書順で訪問
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)
 
    return order
 
g = {0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 3], 3: [1, 2, 4], 4: [3]}
print(dfs_recursive(g, 0))  # [0, 1, 2, 3, 4]
print(dfs_iterative(g, 0))  # [0, 1, 2, 3, 4]

class DFSWithTimestamp:
    """タイムスタンプ付き DFS
    辺の分類やトポロジカルソートに必要な情報を収集する
    """
    def __init__(self, graph: dict):
        self.graph = graph
        self.discovery = {}   # 発見時刻
        self.finish = {}      # 完了時刻
        self.parent = {}      # DFS木における親
        self.time = 0
 
    def dfs(self):
        """全頂点から DFS を実行"""
        all_vertices = set(self.graph.keys())
        for neighbors in self.graph.values():
            all_vertices.update(neighbors)
 
        for v in all_vertices:
            if v not in self.discovery:
                self.parent[v] = None
                self._visit(v)
 
    def _visit(self, u):
        self.time += 1
        self.discovery[u] = self.time
 
        for v in self.graph.get(u, []):
            if v not in self.discovery:
                self.parent[v] = u
                self._visit(v)
 
        self.time += 1
        self.finish[u] = self.time
 
    def classify_edge(self, u, v):
        """辺 (u, v) を分類する"""
        if self.parent.get(v) == u:
            return "tree"      # 木辺
        elif (self.discovery[u] < self.discovery[v] and
              self.finish[u] > self.finish[v]):
            return "forward"   # 前方辺
        elif (self.discovery[u] > self.discovery[v] and
              self.finish[u] < self.finish[v]):
            return "back"      # 後退辺（サイクルを示す）
        else:
            return "cross"     # 交差辺
 
# 使用例
g_directed = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': ['E'],
    'E': [],
}
dfs_ts = DFSWithTimestamp(g_directed)
dfs_ts.dfs()
print("発見時刻:", dfs_ts.discovery)
print("完了時刻:", dfs_ts.finish)

def find_connected_components(graph: dict, vertices: set) -> list:
    """無向グラフの連結成分を列挙"""
    visited = set()
    components = []
 
    for v in vertices:
        if v not in visited:
            component = []
            stack = [v]
            while stack:
                node = stack.pop()
                if node not in visited:
                    visited.add(node)
                    component.append(node)
                    for neighbor in graph.get(node, []):
                        if neighbor not in visited:
                            stack.append(neighbor)
            components.append(component)
 
    return components
 
# 切断されたグラフ
g2 = {0: [1], 1: [0], 2: [3], 3: [2], 4: []}
print(find_connected_components(g2, {0,1,2,3,4}))
# [[0, 1], [2, 3], [4]]

def has_cycle_directed(graph: dict) -> bool:
    """有向グラフのサイクル検出（3色法）"""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = defaultdict(int)  # 全頂点 WHITE
 
    def dfs(u):
        color[u] = GRAY  # 探索中
        for v in graph.get(u, []):
            if color[v] == GRAY:  # 探索中の頂点に戻った → サイクル
                return True
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK  # 探索完了
        return False
 
    for vertex in graph:
        if color[vertex] == WHITE:
            if dfs(vertex):
                return True
    return False
 
def has_cycle_undirected(graph: dict) -> bool:
    """無向グラフのサイクル検出"""
    visited = set()
 
    def dfs(v, parent):
        visited.add(v)
        for neighbor in graph.get(v, []):
            if neighbor not in visited:
                if dfs(neighbor, v):
                    return True
            elif neighbor != parent:
                return True  # 親以外の訪問済み頂点 → サイクル
        return False
 
    for vertex in graph:
        if vertex not in visited:
            if dfs(vertex, None):
                return True
    return False
 
# サイクルあり: 0 → 1 → 2 → 0
g_cycle = {0: [1], 1: [2], 2: [0]}
print(has_cycle_directed(g_cycle))  # True
 
# サイクルなし: DAG
g_dag = {0: [1], 1: [2], 2: []}
print(has_cycle_directed(g_dag))  # False
 
# 無向グラフのサイクル
g_undirected_cycle = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
print(has_cycle_undirected(g_undirected_cycle))  # True

def find_cycle_directed(graph: dict) -> list:
    """有向グラフでサイクルを1つ見つけて経路を返す"""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = defaultdict(int)
    parent = {}
    cycle_start = None
    cycle_end = None
 
    def dfs(u):
        nonlocal cycle_start, cycle_end
        color[u] = GRAY
        for v in graph.get(u, []):
            if color[v] == GRAY:
                cycle_start = v
                cycle_end = u
                return True
            if color[v] == WHITE:
                parent[v] = u
                if dfs(v):
                    return True
        color[u] = BLACK
        return False
 
    for vertex in graph:
        if color[vertex] == WHITE:
            parent[vertex] = None
            if dfs(vertex):
                break
 
    if cycle_start is None:
        return []
 
    # サイクルの経路を復元
    cycle = [cycle_start]
    current = cycle_end
    while current != cycle_start:
        cycle.append(current)
        current = parent[current]
    cycle.reverse()
    return cycle
 
g_cycle = {0: [1], 1: [2], 2: [3], 3: [1]}
print(find_cycle_directed(g_cycle))  # [1, 2, 3]

def topological_sort_dfs(graph: dict) -> list:
    """DFS ベースのトポロジカルソート - O(V + E)"""
    visited = set()
    stack = []  # 結果を逆順に積む
 
    def dfs(v):
        visited.add(v)
        for neighbor in graph.get(v, []):
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(v)  # 帰りがけに追加
 
    # 全頂点から DFS
    all_vertices = set(graph.keys())
    for v in graph.values():
        all_vertices.update(v)
 
    for vertex in all_vertices:
        if vertex not in visited:
            dfs(vertex)
 
    return stack[::-1]  # 逆順が答え
 
dag = {
    "数学": ["物理", "線形代数"],
    "物理": ["量子力学"],
    "線形代数": ["量子力学"],
    "プログラミング": ["アルゴリズム"],
    "量子力学": [],
    "アルゴリズム": [],
}
print(topological_sort_dfs(dag))

def topological_sort_kahn(graph: dict) -> list:
    """Kahn のアルゴリズム（入次数ベース）- O(V + E)"""
    # 全頂点を収集
    all_vertices = set(graph.keys())
    for neighbors in graph.values():
        all_vertices.update(neighbors)
 
    # 入次数を計算
    in_degree = {v: 0 for v in all_vertices}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
 
    # 入次数 0 の頂点をキューに
    queue = deque([v for v in all_vertices if in_degree[v] == 0])
    result = []
 
    while queue:
        vertex = queue.popleft()
        result.append(vertex)
 
        for neighbor in graph.get(vertex, []):
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
 
    if len(result) != len(all_vertices):
        raise ValueError("サイクルが存在します")
 
    return result
 
print(topological_sort_kahn(dag))

def all_topological_sorts(graph: dict) -> list:
    """全トポロジカル順序を列挙（バックトラッキング）"""
    all_vertices = set(graph.keys())
    for neighbors in graph.values():
        all_vertices.update(neighbors)
 
    in_degree = {v: 0 for v in all_vertices}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
 
    result = []
    current = []
    visited = set()
 
    def backtrack():
        if len(current) == len(all_vertices):
            result.append(current[:])
            return
 
        for v in sorted(all_vertices):
            if v not in visited and in_degree[v] == 0:
                # 選択
                visited.add(v)
                current.append(v)
                for neighbor in graph.get(v, []):
                    in_degree[neighbor] -= 1
 
                backtrack()
 
                # 取り消し
                visited.discard(v)
                current.pop()
                for neighbor in graph.get(v, []):
                    in_degree[neighbor] += 1
 
    backtrack()
    return result
 
# 小さなDAGの例
small_dag = {'A': ['C'], 'B': ['C'], 'C': []}
print(all_topological_sorts(small_dag))
# [['A', 'B', 'C'], ['B', 'A', 'C']]

# 実務例1: ビルドシステムの依存関係解決
build_deps = {
    "utils.o": ["utils.c", "utils.h"],
    "main.o": ["main.c", "utils.h"],
    "app": ["main.o", "utils.o"],
    "utils.c": [],
    "utils.h": [],
    "main.c": [],
}
 
def build_order(deps: dict) -> list:
    """ビルド順序を決定"""
    # 依存関係を逆転（A depends on B → B → A）
    graph = defaultdict(list)
    all_files = set(deps.keys())
    for target, sources in deps.items():
        for src in sources:
            graph[src].append(target)
            all_files.add(src)
 
    # Kahn のアルゴリズム
    in_deg = {f: 0 for f in all_files}
    for u in graph:
        for v in graph[u]:
            in_deg[v] += 1
 
    queue = deque([f for f in all_files if in_deg[f] == 0])
    order = []
    while queue:
        f = queue.popleft()
        order.append(f)
        for dep in graph[f]:
            in_deg[dep] -= 1
            if in_deg[dep] == 0:
                queue.append(dep)
 
    return order
 
print(build_order(build_deps))
# ['utils.c', 'utils.h', 'main.c', 'utils.o', 'main.o', 'app']
 
 
# 実務例2: タスクスケジューリング（並列実行可能なタスクの識別）
def schedule_tasks_parallel(graph: dict) -> list:
    """並列実行可能なタスクをステージごとにまとめる"""
    all_vertices = set(graph.keys())
    for neighbors in graph.values():
        all_vertices.update(neighbors)
 
    in_degree = {v: 0 for v in all_vertices}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
 
    queue = deque([v for v in all_vertices if in_degree[v] == 0])
    stages = []
 
    while queue:
        stage = []
        next_queue = deque()
        while queue:
            v = queue.popleft()
            stage.append(v)
            for neighbor in graph.get(v, []):
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    next_queue.append(neighbor)
        stages.append(stage)
        queue = next_queue
 
    return stages
 
task_deps = {
    'compile_a': ['link'],
    'compile_b': ['link'],
    'compile_c': ['link'],
    'link': ['test'],
    'test': ['deploy'],
    'deploy': [],
}
print(schedule_tasks_parallel(task_deps))
# [['compile_a', 'compile_b', 'compile_c'], ['link'], ['test'], ['deploy']]

def kosaraju_scc(graph: dict) -> list:
    """Kosaraju のアルゴリズム - O(V + E)
    1. 元グラフで DFS → 完了順に頂点を記録
    2. グラフの転置を作成
    3. 転置グラフ上で、完了順の逆順に DFS → 各 DFS で到達する頂点が SCC
    """
    # 全頂点を収集
    all_vertices = set(graph.keys())
    for neighbors in graph.values():
        all_vertices.update(neighbors)
 
    # Step 1: 元グラフで DFS、完了順を記録
    visited = set()
    finish_order = []
 
    def dfs1(v):
        visited.add(v)
        for neighbor in graph.get(v, []):
            if neighbor not in visited:
                dfs1(neighbor)
        finish_order.append(v)
 
    for v in all_vertices:
        if v not in visited:
            dfs1(v)
 
    # Step 2: 転置グラフの作成
    transpose = defaultdict(list)
    for u in graph:
        for v in graph[u]:
            transpose[v].append(u)
 
    # Step 3: 転置グラフ上で逆順に DFS
    visited.clear()
    sccs = []
 
    def dfs2(v, component):
        visited.add(v)
        component.append(v)
        for neighbor in transpose.get(v, []):
            if neighbor not in visited:
                dfs2(neighbor, component)
 
    for v in reversed(finish_order):
        if v not in visited:
            component = []
            dfs2(v, component)
            sccs.append(component)
 
    return sccs
 
# 使用例
g_scc = {
    0: [1],
    1: [2],
    2: [0, 3],  # 0→1→2→0 がSCC
    3: [4],
    4: [5],
    5: [3],     # 3→4→5→3 がSCC
}
print(kosaraju_scc(g_scc))
# [[0, 2, 1], [3, 5, 4]] （順序は異なりうる）

def tarjan_scc(graph: dict) -> list:
    """Tarjan の SCC アルゴリズム - O(V + E)
    DFS 1回で全 SCC を発見（Kosaraju より実用的）
    """
    index_counter = [0]
    stack = []
    lowlink = {}
    index = {}
    on_stack = set()
    sccs = []
 
    all_vertices = set(graph.keys())
    for neighbors in graph.values():
        all_vertices.update(neighbors)
 
    def strongconnect(v):
        index[v] = index_counter[0]
        lowlink[v] = index_counter[0]
        index_counter[0] += 1
        stack.append(v)
        on_stack.add(v)
 
        for w in graph.get(v, []):
            if w not in index:
                strongconnect(w)
                lowlink[v] = min(lowlink[v], lowlink[w])
            elif w in on_stack:
                lowlink[v] = min(lowlink[v], index[w])
 
        # v がルートなら SCC を取り出す
        if lowlink[v] == index[v]:
            component = []
            while True:
                w = stack.pop()
                on_stack.discard(w)
                component.append(w)
                if w == v:
                    break
            sccs.append(component)
 
    for v in all_vertices:
        if v not in index:
            strongconnect(v)
 
    return sccs
 
print(tarjan_scc(g_scc))

def bfs_grid(grid: list, start: tuple, end: tuple) -> int:
    """2Dグリッド上の最短経路（BFS）"""
    rows, cols = len(grid), len(grid[0])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 右左下上
 
    visited = {start}
    queue = deque([(start, 0)])  # (位置, 距離)
 
    while queue:
        (r, c), dist = queue.popleft()
        if (r, c) == end:
            return dist
 
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols and
                grid[nr][nc] != 1 and (nr, nc) not in visited):
                visited.add((nr, nc))
                queue.append(((nr, nc), dist + 1))
 
    return -1  # 到達不可能
 
# 0: 通路, 1: 壁
maze = [
    [0, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 0, 0, 0],
    [0, 1, 1, 0],
]
print(bfs_grid(maze, (0, 0), (3, 3)))  # 6

def bfs_grid_8dir(grid: list, start: tuple, end: tuple) -> int:
    """8方向移動の最短経路"""
    rows, cols = len(grid), len(grid[0])
    # 8方向: 上下左右 + 斜め4方向
    directions = [
        (-1, -1), (-1, 0), (-1, 1),
        (0, -1),           (0, 1),
        (1, -1),  (1, 0),  (1, 1),
    ]
 
    visited = {start}
    queue = deque([(start, 0)])
 
    while queue:
        (r, c), dist = queue.popleft()
        if (r, c) == end:
            return dist
 
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols and
                grid[nr][nc] != 1 and (nr, nc) not in visited):
                visited.add((nr, nc))
                queue.append(((nr, nc), dist + 1))
 
    return -1

def bfs_grid_with_path(grid: list, start: tuple, end: tuple) -> list:
    """2Dグリッドで最短経路を復元"""
    rows, cols = len(grid), len(grid[0])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
 
    visited = {start}
    parent = {start: None}
    queue = deque([start])
 
    while queue:
        r, c = queue.popleft()
        if (r, c) == end:
            # 経路復元
            path = []
            current = end
            while current is not None:
                path.append(current)
                current = parent[current]
            return path[::-1]
 
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols and
                grid[nr][nc] != 1 and (nr, nc) not in visited):
                visited.add((nr, nc))
                parent[(nr, nc)] = (r, c)
                queue.append((nr, nc))
 
    return []  # 到達不可能
 
path = bfs_grid_with_path(maze, (0, 0), (3, 3))
print(path)
# [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (3, 3)]

def find_articulation_points_and_bridges(graph: dict, vertices: set):
    """関節点と橋の検出 - O(V + E)"""
    discovery = {}
    low = {}
    parent = {}
    ap = set()          # 関節点
    bridges = []        # 橋
    time_counter = [0]
 
    def dfs(u):
        discovery[u] = low[u] = time_counter[0]
        time_counter[0] += 1
        children = 0
 
        for v in graph.get(u, []):
            if v not in discovery:
                children += 1
                parent[v] = u
                dfs(v)
                low[u] = min(low[u], low[v])
 
                # u がルートで子が2つ以上 → 関節点
                if parent[u] is None and children > 1:
                    ap.add(u)
 
                # u がルートでなく、子の lowlink が u の discovery 以上 → 関節点
                if parent[u] is not None and low[v] >= discovery[u]:
                    ap.add(u)
 
                # 橋の条件: low[v] > discovery[u]
                if low[v] > discovery[u]:
                    bridges.append((u, v))
            elif v != parent.get(u):
                low[u] = min(low[u], discovery[v])
 
    for v in vertices:
        if v not in discovery:
            parent[v] = None
            dfs(v)
 
    return ap, bridges
 
# 使用例
g_bridge = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3],
    3: [2, 4],
    4: [3],
}
ap, bridges = find_articulation_points_and_bridges(g_bridge, {0,1,2,3,4})
print(f"関節点: {ap}")     # {2, 3}
print(f"橋: {bridges}")    # [(2, 3), (3, 4)]

def find_euler_path(graph: dict) -> list:
    """Hierholzer のアルゴリズムでオイラー路/回路を求める
    graph: 隣接リスト（辺のリスト）、辺は消費される
    """
    # グラフのコピー（辺を消費するため）
    adj = defaultdict(list)
    for u in graph:
        for v in graph[u]:
            adj[u].append(v)
 
    # 始点の決定
    odd_vertices = [v for v in adj if len(adj[v]) % 2 == 1]
    if len(odd_vertices) == 0:
        start = next(iter(adj))  # オイラー回路: 任意の頂点
    elif len(odd_vertices) == 2:
        start = odd_vertices[0]   # オイラー路: 奇数次数頂点から
    else:
        return []  # オイラー路/回路は存在しない
 
    stack = [start]
    path = []
 
    while stack:
        v = stack[-1]
        if adj[v]:
            u = adj[v].pop()
            # 無向グラフの場合、逆辺も削除
            adj[u].remove(v)
            stack.append(u)
        else:
            path.append(stack.pop())
 
    return path[::-1]
 
# ケーニヒスベルクの橋（オイラーが解けないことを証明した問題の変形）
g_euler = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['B', 'B', 'C'],
}
path = find_euler_path(g_euler)
print(f"オイラー路: {path}")

def mutual_friends(graph: dict, u, v) -> set:
    """共通の友人を見つける"""
    friends_u = set(graph.get(u, []))
    friends_v = set(graph.get(v, []))
    return friends_u & friends_v
 
def degrees_of_separation(graph: dict, u, v) -> int:
    """2人の間の隔たりの次数（最短距離）"""
    if u == v:
        return 0
    visited = {u}
    queue = deque([(u, 0)])
    while queue:
        node, dist = queue.popleft()
        for neighbor in graph.get(node, []):
            if neighbor == v:
                return dist + 1
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return -1  # 非連結
 
def influence_score(graph: dict, start, max_depth: int = 3) -> int:
    """影響力スコア: max_depth ホップ以内に到達可能な頂点数"""
    visited = {start}
    queue = deque([(start, 0)])
    while queue:
        node, depth = queue.popleft()
        if depth >= max_depth:
            continue
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, depth + 1))
    return len(visited) - 1  # 自分を除く

def web_crawler_bfs(start_url: str, max_pages: int = 100) -> list:
    """BFS ベースのウェブクローラ（概念的な実装）"""
    visited = {start_url}
    queue = deque([start_url])
    crawled = []
 
    while queue and len(crawled) < max_pages:
        url = queue.popleft()
        crawled.append(url)
 
        # 実際には HTTP リクエストでページを取得し、リンクを抽出する
        links = extract_links(url)  # 仮想関数
 
        for link in links:
            if link not in visited:
                visited.add(link)
                queue.append(link)
 
    return crawled
 
def extract_links(url):
    """仮想的なリンク抽出（実際にはHTMLパースが必要）"""
    return []  # プレースホルダ

def detect_deadlock(resource_graph: dict) -> list:
    """リソース割り当てグラフでデッドロック（サイクル）を検出"""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = defaultdict(int)
    path = []
    cycle = []
 
    def dfs(u):
        color[u] = GRAY
        path.append(u)
        for v in resource_graph.get(u, []):
            if color[v] == GRAY:
                # サイクル発見 → デッドロック
                idx = path.index(v)
                cycle.extend(path[idx:])
                return True
            if color[v] == WHITE and dfs(v):
                return True
        path.pop()
        color[u] = BLACK
        return False
 
    for vertex in resource_graph:
        if color[vertex] == WHITE:
            if dfs(vertex):
                return cycle
 
    return []  # デッドロックなし
 
# プロセス P1 → リソース R1 → プロセス P2 → リソース R2 → P1
resource_graph = {
    'P1': ['R1'],
    'R1': ['P2'],
    'P2': ['R2'],
    'R2': ['P1'],
}
deadlock = detect_deadlock(resource_graph)
print(f"デッドロック: {deadlock}")
# デッドロック: ['P1', 'R1', 'P2', 'R2']

# BAD: キューから取り出した時に visited チェック
# → 同じ頂点が複数回キューに入り、メモリと時間を浪費
def bad_bfs(graph, start):
    queue = deque([start])
    visited = set()
    while queue:
        v = queue.popleft()
        if v in visited:  # ここでチェック → 遅い
            continue
        visited.add(v)
        for n in graph[v]:
            queue.append(n)  # 重複追加される
 
# GOOD: キューに追加する時に visited チェック
def good_bfs(graph, start):
    queue = deque([start])
    visited = {start}  # 追加時にマーク
    while queue:
        v = queue.popleft()
        for n in graph[v]:
            if n not in visited:
                visited.add(n)  # ここでマーク
                queue.append(n)

# BAD: 大きなグラフで再帰 DFS → RecursionError
import sys
sys.setrecursionlimit(10**6)  # 応急処置だが不安定
 
# GOOD: 反復版 DFS を使用
def safe_dfs(graph, start):
    visited = set()
    stack = [start]
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.add(v)
            for n in graph.get(v, []):
                if n not in visited:
                    stack.append(n)

# BAD: 頂点数 100,000 の疎グラフに隣接行列
# → メモリ 100,000 × 100,000 = 10^10 要素 → メモリ不足
n = 100000
matrix = [[0] * n for _ in range(n)]  # MemoryError!
 
# GOOD: 隣接リストを使う
graph = defaultdict(list)
# 辺数 E << V^2 なので、メモリは O(V + E) で済む

# BAD: パスを毎回コピー → O(V^2) メモリ
def bad_bfs_path(graph, start, end):
    queue = deque([(start, [start])])  # パス全体をコピー
    visited = {start}
    while queue:
        v, path = queue.popleft()
        if v == end:
            return path
        for n in graph[v]:
            if n not in visited:
                visited.add(n)
                queue.append((n, path + [n]))  # O(V) のコピー
 
# GOOD: 前任者辞書を使って後から復元 → O(V) メモリ
def good_bfs_path(graph, start, end):
    prev = {start: None}
    queue = deque([start])
    while queue:
        v = queue.popleft()
        if v == end:
            path = []
            while v is not None:
                path.append(v)
                v = prev[v]
            return path[::-1]
        for n in graph[v]:
            if n not in prev:
                prev[n] = v
                queue.append(n)
    return []

# 演習1: 基本実装のテンプレート
class Exercise1:
    """基本的な実装パターンの演習"""
 
    def __init__(self):
        self.data = []
 
    def validate_input(self, value):
        """入力値の検証"""
        if value is None:
            raise ValueError("入力値がNoneです")
        return True
 
    def process(self, value):
        """データ処理のメインロジック"""
        self.validate_input(value)
        self.data.append(value)
        return self.data
 
    def get_results(self):
        """処理結果の取得"""
        return {
            'count': len(self.data),
            'data': self.data
        }
 
# テスト
def test_exercise1():
    ex = Exercise1()
    assert ex.process(1) == [1]
    assert ex.process(2) == [1, 2]
    assert ex.get_results()['count'] == 2
 
    try:
        ex.process(None)
        assert False, "例外が発生するべき"
    except ValueError:
        pass
 
    print("全テスト合格!")
 
test_exercise1()

# 演習2: 応用パターン
from typing import List, Dict, Optional
from datetime import datetime
 
class AdvancedExercise:
    """応用パターンの演習"""
 
    def __init__(self, max_size: int = 100):
        self._items: List[Dict] = []
        self._max_size = max_size
        self._created_at = datetime.now()
 
    def add(self, key: str, value: any) -> bool:
        """アイテムの追加（サイズ制限付き）"""
        if len(self._items) >= self._max_size:
            return False
        self._items.append({
            'key': key,
            'value': value,
            'timestamp': datetime.now().isoformat()
        })
        return True
 
    def find(self, key: str) -> Optional[Dict]:
        """キーによる検索"""
        for item in reversed(self._items):
            if item['key'] == key:
                return item
        return None
 
    def remove(self, key: str) -> bool:
        """キーによる削除"""
        for i, item in enumerate(self._items):
            if item['key'] == key:
                self._items.pop(i)
                return True
        return False
 
    def stats(self) -> Dict:
        """統計情報"""
        return {
            'total_items': len(self._items),
            'max_size': self._max_size,
            'usage_percent': len(self._items) / self._max_size * 100,
            'uptime': str(datetime.now() - self._created_at)
        }
 
# テスト
def test_advanced():
    ex = AdvancedExercise(max_size=3)
    assert ex.add("a", 1) == True
    assert ex.add("b", 2) == True
    assert ex.add("c", 3) == True
    assert ex.add("d", 4) == False  # サイズ制限
    assert ex.find("b")['value'] == 2
    assert ex.remove("b") == True
    assert ex.find("b") is None
    stats = ex.stats()
    assert stats['total_items'] == 2
    print("応用テスト全合格!")
 
test_advanced()

# 演習3: パフォーマンス最適化
import time
from functools import lru_cache
 
# 最適化前（O(n^2)）
def slow_search(data: list, target: int) -> int:
    """非効率な検索"""
    for i in range(len(data)):
        for j in range(i + 1, len(data)):
            if data[i] + data[j] == target:
                return (i, j)
    return (-1, -1)
 
# 最適化後（O(n)）
def fast_search(data: list, target: int) -> tuple:
    """ハッシュマップを使った効率的な検索"""
    seen = {}
    for i, num in enumerate(data):
        complement = target - num
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i
    return (-1, -1)
 
# ベンチマーク
def benchmark():
    import random
    data = list(range(5000))
    random.shuffle(data)
    target = data[100] + data[4000]
 
    start = time.time()
    result1 = slow_search(data, target)
    slow_time = time.time() - start
 
    start = time.time()
    result2 = fast_search(data, target)
    fast_time = time.time() - start
 
    print(f"非効率版: {slow_time:.4f}秒")
    print(f"効率版:   {fast_time:.6f}秒")
    print(f"高速化率: {slow_time/fast_time:.0f}倍")
 
benchmark()

def bidirectional_bfs(graph: dict, start, end) -> int:
    """双方向BFS - 始点と終点から同時に探索"""
    if start == end:
        return 0
 
    front = {start}
    back = {end}
    visited_front = {start: 0}
    visited_back = {end: 0}
    depth = 0
 
    while front and back:
        depth += 1
        # 小さい方を拡張（効率化）
        if len(front) > len(back):
            front, back = back, front
            visited_front, visited_back = visited_back, visited_front
 
        next_front = set()
        for v in front:
            for neighbor in graph.get(v, []):
                if neighbor in visited_back:
                    return visited_front[v] + 1 + visited_back[neighbor]
                if neighbor not in visited_front:
                    visited_front[neighbor] = depth
                    next_front.add(neighbor)
 
        front = next_front
 
    return -1  # 到達不可能