[Programmers] 도넛과 막대 그래프

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/258711

프로그래머스

edges, a, b 모두 최대 100만이기 때문에 브루트포스로 풀기보다는 규칙을 찾아 풀어야 하는 문제였습니다.
 
규칙은 아래와 같습니다.
1. 모든 그래프는 생성한 정점으로부터 파생됩니다. 문제 조건에서 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다 라고 명시했으므로 해당 정점을 향하는 간선은 0개, 해당 정점으로부터 다른 정점으로 나가는 간선은 최소 2개입니다.
2. 막대 모양 그래프의 특징을 보면 최상위 노드로부터 다른 노드로 향하는 간선이 없습니다.
3. 8자 모양 그래프의 가운데 정점을 보면 유일하게 해당 정점으로 향하는 간선이 2개 이상, 해당 정점으로부터 다른 정점으로 향하는 간선은 2개인 것을 확인할 수 있습니다.

3.1 8자 모양 그래프 자체로만 봤을 때는 가운데 정점 기준 나가는 간선, 향하는 간선 모두 2개이지만 "생성한 정점"으로부터 향하는 간선이 8자 모양 그래프의 가운데 정점을 향하는 경우 input이 3이 됩니다.
4. 도넛 모양 그래프의 경우 별다른 특징이 없으므로 아래와 같은 수식을 통해 구할 수 있습니다.
4.1 생성한 정점으로부터 파생된 그래프의 수 - (막대 모양 그래프의 수 + 8자 모양 그래프의 수)
 

 
 
개발환경: Programmers IDE 
 
지적, 조언, 질문 환영합니다! 질문 남겨주세요~