31002: 그래프 변환 (월간 향유회 2023.12.D번)
·
PS/BOJ
시간 제한 메모리 제한 1초 1024MB 문제 그래프의 변환(f:g↦g′)을 다음과 같이 정의한다. G의 간선을 G'의 정점으로 보고 G의 인접한 간선끼리 G'에서 간선으로 연결하여 G에서 인접하였음을 나타낸다. 서로 다른 두 간선이 같은 정점을 하나 이상 공유하면 두 간선이 인접한다고 표현한다. 다음은 그래프 변환의 예시 중 하나이다. 그리고 변환한 그래프를 다시 변환하는 것도 가능하다. N-완전 그래프를 K번 변환한 그래프의 정점이 몇 개인지 구하시오. N-완전 그래프는 정점이 N개인 그래프에서 서로 다른 두 정점에 대해 반드시 간선이 존재하는 그래프이다. 입력 첫째 줄에 정수 N, K가 공백을 사이에 두고 주어진다. (3 ≤ N ≤ 100,000, 0 ≤ K ≤ 100,000) 출력 K번 변환한 그..
전라남도교육지원청
'그래프이론' 태그의 글 목록