그래프에서 서로 연결된 세 정점의 차수 합의 최솟값 찾기

17089번: 세 친구 (acmicpc.net) 서로 친구인 a,b,c에 대하여 a의 친구 수 + b의 친구 수 + c의 친구 수가 최소가 되도록 만들고 싶다. a의 친구 수에는 b,c는 제외해야한다. 마찬가지로 b,c의 친구 수에는 a,c, a,b는 제외해야한다. a의 친구 수 + b의 친구 수 + c의 친구 수 - 6의 최솟값을 찾아야한다는 소리 친구 관계를 그래프로 만드는데 각 정점에 연결된 정점을 set()으로 만들어서 O(1)로 서로 친구인 정점을 찾도록 만들자 from sys import stdinn,m = map(int,stdin.readline().split())graph = [set() for _ in range(n+1)]for _ in range(m): a,b = map(int,s..

• format_list_bulleted 브루트포스
• · 2024. 9. 10.
• textsms

트리 이론 기본편1 -용어 정리-

1. 트리의 개념 비선형 구조 원소들 간에 1:n 관계를 가지는 자료구조 원소들 간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 구조 ############### 선형구조와 비선형구조 간단히 ################################# 2. 트리의 정의 1개 이상의 노드로 이루어진 유한 집합 즉, 노드가 1개만 있어도 트리 최상위 노드를 root라고 부른다 루트 이외의 나머지 노드들은 n개의 부분집합 $T_{1}, T_{2}, T_{3},... , T_{n}$으로 분리 가능하다 그림과 같이 $T_{1}, T_{2}, T_{3},... , T_{n}$도 하나의 트리가 되며, 루트의 부 트리(subtree)가 된다 그러니까 어떤 tree의 일..

• format_list_bulleted 그래프 이론 정복기
• · 2022. 9. 13.
• textsms