[백준/그래프] 13023 ABCDE (Python, 파이썬)

 

https://www.acmicpc.net/problem/13023

13023번: ABCDE

 

import sys

n, m = map(int, input().split())
edges = []
a = [[False] * n for _ in range(n)]
g = [[] for _ in range(n)]

for _ in range(m):
    u, v = map(int, input().split())
    # 방향이 없는 그래프로 양방향 모두 입력
    edges.append((u, v))
    edges.append((v, u))

    # a: 서로 연결되어 있으며 True
    a[u][v] = a[v][u] = True

    # g: u정점에는 v로 가는 간선이 있음
    g[u].append(v)
    g[v].append(u)

m *= 2
for i in range(m):
    for j in range(m):
        A, B = edges[i]
        C, D = edges[j]

        if A == B or A == C or A == D or B == C or B == D or C == D:
            continue
        
        if not a[B][C]:
            continue

        for E in g[D]:
            if A == E or B == E or C == E or D == E:
                continue
            print(1)
            sys.exit(0)
print(0)