結果

問題 No.408 五輪ピック
ユーザー gew1fw
提出日時 2025-06-12 19:02:21
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,408 bytes
コンパイル時間 432 ms
コンパイル使用メモリ 82,608 KB
実行使用メモリ 176,392 KB
最終ジャッジ日時 2025-06-12 19:02:32
合計ジャッジ時間 9,348 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23 MLE * 5 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

from sys import stdin

def main():
    input = stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx += 1
    m = int(input[idx])
    idx += 1
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = int(input[idx])
        idx += 1
        v = int(input[idx])
        idx += 1
        adj[u].append(v)
        adj[v].append(u)
    # Collect neighbors of vertex 1
    s = set()
    for neighbor in adj[1]:
        s.add(neighbor)
    if not s:
        print("NO")
        return
    found = False
    # Check each neighbor of 1
    for a in s:
        # DFS stack: (current node, depth, visited set)
        stack = [(a, 0, {1, a})]
        while stack:
            node, depth, visited = stack.pop()
            if depth == 3:
                if node in s and node != a:
                    found = True
                    break
                continue
            # Explore neighbors in reverse order to process smaller indices first (stack order)
            for neighbor in reversed(adj[node]):
                if neighbor == 1:
                    continue
                if neighbor not in visited:
                    new_visited = visited.copy()
                    new_visited.add(neighbor)
                    stack.append((neighbor, depth + 1, new_visited))
        if found:
            break
    print("YES" if found else "NO")

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