結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー lam6er
提出日時 2025-03-20 18:48:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 365 ms / 2,000 ms
コード長 2,675 bytes
コンパイル時間 153 ms
コンパイル使用メモリ 82,724 KB
実行使用メモリ 103,432 KB
最終ジャッジ日時 2025-03-20 18:49:54
合計ジャッジ時間 4,146 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin

def main():
    N = int(stdin.readline())
    edges = []
    graph = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, stdin.readline().split())
        edges.append((u, v))
        graph[u].append(v)
        graph[v].append(u)
    
    # Union-Find to count connected components
    class UnionFind:
        def __init__(self, size):
            self.parent = list(range(size))
        
        def find(self, x):
            if self.parent[x] != x:
                self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
        
        def unite(self, x, y):
            x_root = self.find(x)
            y_root = self.find(y)
            if x_root == y_root:
                return False
            self.parent[y_root] = x_root
            return True
    
    uf = UnionFind(N)
    for u, v in edges:
        uf.unite(u, v)
    
    parents = [uf.find(i) for i in range(N)]
    c = len(set(parents))  # Number of connected components
    
    # Tarjan's algorithm to find bridges (non-recursive)
    order = [-1] * N
    low = [-1] * N
    bridges = []
    order_index = 0
    
    for u in range(N):
        if order[u] == -1:
            stack = [(u, -1, False)]  # (vertex, parent, visited)
            while stack:
                v, parent, visited = stack.pop()
                if not visited:
                    if order[v] != -1:
                        continue
                    order[v] = order_index
                    low[v] = order_index
                    order_index += 1
                    stack.append((v, parent, True))
                    # Process children in reverse to maintain order
                    for w in reversed(graph[v]):
                        if w == parent:
                            continue
                        if order[w] == -1:
                            stack.append((w, v, False))
                        else:
                            low[v] = min(low[v], order[w])
                else:
                    for w in graph[v]:
                        if w == parent:
                            continue
                        if order[w] > order[v]:  # Child processed after v
                            low[v] = min(low[v], low[w])
                            if low[w] > order[v]:
                                bridges.append((v, w))
                        else:
                            low[v] = min(low[v], order[w])
    has_bridge = len(bridges) > 0
    
    if not has_bridge:
        print("Alice" if c >= 3 else "Bob")
    else:
        print("Alice" if c >= 2 else "Bob")

if __name__ == "__main__":
    main()
0