結果

問題 No.488 四角関係
ユーザー lam6er
提出日時 2025-03-20 20:30:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 154 ms / 5,000 ms
コード長 915 bytes
コンパイル時間 201 ms
コンパイル使用メモリ 82,536 KB
実行使用メモリ 76,528 KB
最終ジャッジ日時 2025-03-20 20:31:29
合計ジャッジ時間 2,768 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import itertools

n, m = map(int, input().split())
adj = [[False] * n for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    adj[a][b] = True
    adj[b][a] = True

count = 0

# Iterate through all possible quartets of 4 distinct nodes
for quartet in itertools.combinations(range(n), 4):
    # Check if there are exactly 4 edges within the quartet
    edge_count = 0
    for u, v in itertools.combinations(quartet, 2):
        if adj[u][v]:
            edge_count += 1
    if edge_count != 4:
        continue
    
    # Check each node in the quartet has exactly two edges within the quartet
    valid = True
    for node in quartet:
        connections = 0
        for other in quartet:
            if other != node and adj[node][other]:
                connections += 1
        if connections != 2:
            valid = False
            break
    if valid:
        count += 1

print(count)
0