#1165521 (PyPy3) No.3234 Infinite Propagation

• 問題: No.3234 Infinite Propagation
• ユーザー: flippergo
• 提出日時: 2026-05-19 11:40:29
• 言語: PyPy3 (7.3.17)
• 結果: AC
• 実行時間: 646 ms / 2,000 ms
• コード長: 5,518 bytes
• コンパイル時間: 254 ms
• コンパイル使用メモリ: 84,736 KB
• 実行使用メモリ: 146,796 KB
• 最終ジャッジ日時: 2026-05-19 11:40:37
• 合計ジャッジ時間: 7,488 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 18

ソースコード

from collections import deque

class AhoCorasick:
    def __init__(self):
        self.next = [dict()]
        self.fail = [0]
        self.out = [[]]
        self.out_link = [0]

    def add(self, pattern: str, pattern_id: int) -> None:
        v = 0

        for ch in pattern:
            if ch not in self.next[v]:
                new_node = len(self.next)
                self.next[v][ch] = new_node
                self.next.append(dict())
                self.fail.append(0)
                self.out.append([])
                self.out_link.append(0)

            v = self.next[v][ch]

        self.out[v].append(pattern_id)

    def build(self) -> None:
        q = deque()

        for ch, u in self.next[0].items():
            self.fail[u] = 0
            q.append(u)

        while q:
            v = q.popleft()

            # 以前はここで self.out[v].extend(self.out[self.fail[v]]) として、
            # fail 先で見つかるパターンを out[v] にコピーしていました。
            # しかしコピーすると同じ pattern_id が多くのノードに複製され、MLE の原因になります。
            # そこで out_link[v] に「fail をたどった先で、次に out があるノード」を覚えます。
            if self.out[self.fail[v]]:
                self.out_link[v] = self.fail[v]
            else:
                self.out_link[v] = self.out_link[self.fail[v]]

            for ch, u in self.next[v].items():
                f = self.fail[v]

                while f != 0 and ch not in self.next[f]:
                    f = self.fail[f]

                if ch in self.next[f]:
                    self.fail[u] = self.next[f][ch]
                else:
                    self.fail[u] = 0

                q.append(u)

    def search(self, text: str, on_match) -> None:
        v = 0

        for pos, ch in enumerate(text):
            while v != 0 and ch not in self.next[v]:
                v = self.fail[v]

            if ch in self.next[v]:
                v = self.next[v][ch]
            else:
                v = 0

            for pattern_id in self.out[v]:
                # 見つかった結果をリストにためず、その場で呼び出し側に渡します。
                # この問題では「どの位置で見つかったか」は不要なので、
                # pattern_id だけを渡せば十分です。
                on_match(pattern_id)

            # out_link をたどると、fail 先にあるパターンも見つけられます。
            # 例: "she" に到達したとき、out_link で "he" のノードへ進めば、
            # "she" の末尾にある "he" も検出できます。
            # out をコピーしていないので、メモリを増やさずに同じ判定ができます。
            u = self.out_link[v]
            while u != 0:
                for pattern_id in self.out[u]:
                    on_match(pattern_id)
                u = self.out_link[u]
    
T = int(input())
for _ in range(T):
    N = int(input())
    x_to_id = {}
    ys_by_x = []

    for _ in range(N):
        x,y = input().split()

        # 同じ X を持つルールは、同じグラフノードとして扱います。
        # 例: X が "a" のルールが 100 個あっても、ノードは 1 個だけ作ります。
        if x not in x_to_id:
            x_to_id[x] = len(x_to_id)
            ys_by_x.append([])

        ys_by_x[x_to_id[x]].append(y)

    if "a" not in x_to_id:
        print("No")
    else:
        M = len(x_to_id)
        ac = AhoCorasick()

        # Aho-Corasick に入れる X も、重複を除いたものだけにします。
        # pattern_id は「元のルール番号」ではなく「X のグループ番号」です。
        for x, group_id in x_to_id.items():
            ac.add(x, group_id)

        ac.build()

        G = [[] for _ in range(M)]
        for i, y_list in enumerate(ys_by_x):
            seen = set()

            def add_edge(j):
                # 同じ X グループ i から同じ X グループ j への辺は 1 本あれば十分です。
                # i に対応する複数の Y の中で j が何度見つかっても、重複して保存しません。
                if j not in seen:
                    seen.add(j)
                    G[i].append(j)

            # 同じ X を持つ複数のルールは、すべて同じ出発ノード i からの選択肢です。
            # それぞれの Y に含まれる X グループを探し、辺 i -> j を作ります。
            for y in y_list:
                ac.search(y, add_edge)

        que = deque()
        A = set()
        start = x_to_id["a"]
        que.append(start)
        A.add(start)

        while que:
            u = que.popleft()
            for v in G[u]:
                if v not in A:
                    A.add(v)
                    que.append(v)
        B = {i:0 for i in A}
        for i in A:
            for v in G[i]:
                if v in A:
                    B[v] += 1
        que = deque()
        for v in B:
            if B[v] == 0:
                que.append(v)
        while que:
            u = que.popleft()
            for v in G[u]:
                if v in A:
                    B[v] -= 1
                    if B[v] == 0:
                        que.append(v)
        flag = 0
        for v in B:
            flag += B[v]
        if flag==0:
            print("No")
        else:
            print("Yes")