그래프가 주어지고 그래프에서 가장 큰 파벌의 최소 크기를 구하라는 요청을 받았다고 가정합니다. 그래프의 클리크는 모든 정점 쌍이 인접한 그래프의 하위 집합입니다. 즉, 모든 정점 쌍 사이에 가장자리가 있습니다. 그래프에서 가장 큰 클리크를 찾는 것은 다항식 시간에는 불가능하므로 작은 그래프의 노드와 에지의 수를 감안할 때 가장 큰 클리크를 찾아야 합니다.
따라서 입력이 노드 =4와 같으면 가장자리 =4입니다. 그러면 출력은 2가 됩니다.
위 그래프에서 파벌의 최대 크기는 2입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- helper() 함수를 정의합니다. x, y
- ga :=x 모드 y
- gb :=y - ga
- sa :=값의 몫(x / y) + 1
- sb :=(x / y) 값의 몫
- 반환 ga * gb * sa * sb + ga *(ga - 1) * sa * sa / 2 + gb * (GB - 1) * sb * sb / 2
- i :=1
- j :=노드 + 1
- i + 1
- p :=i + ((j - i) / 2)의 하한값
- k :=도우미(노드, p)
- k
- 나 :=피
- j :=p
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
import math def helper(x, y): ga = x % y gb = y - ga sa = x // y + 1 sb = x // y return ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2 def solve(nodes, edges): i = 1 j = nodes + 1 while i + 1 < j: p = i + (j - i) // 2 k = helper(nodes, p) if k < edges: i = p else: j = p return j print(solve(4, 4))
입력
4,4
출력
2