[백준] 1762 : 평면그래프와 삼각형

www.acmicpc.net/problem/1762

1762번: 평면그래프와 삼각형

---

• 삼각형을 세는 기막힌 방법이 있다.
• 먼저 각 노드별로 인접 노드들은 담은 리스트 형태로 구성을 한다.
• 그리고 주어진 엣지들을 전부 탐색하며, 엣지의 양 노드의 교집합의 갯수를 구하면 삼각형의 갯수가 된다.
• 다만 이 경우 삼각형이 중복으로 세어질 수 있기 떄문에, 인접리스트를 구성할 때 자신의 노드값보다 큰 노드들만 담는 식으로 차순을 설정하여 중복을 제거해준다.

---

import sys
n, m = map(int, input().split())
adjs = [set() for i in range(n+1)]
cnt = 0

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    adjs[a].add(b) if a < b else adjs[b].add(a)		# 인접리스트 구성, 자기보다 높은 노드만 담음

for sets in adjs:		# 모든 노드들을 돌며
    for i in sets:		# 해당 노드의 인접 노드들을 돌며
        cnt += len(sets.intersection(adjs[i]))	# 교집합의 갯수를 구함

print(cnt)