문제 설명
정점의 수를 나타내는 정수 N이 주어집니다. 작업은 N 정점의 이분 그래프에서 가능한 최대 모서리 수를 찾는 것입니다.
이분 그래프
- 이분 그래프는 2세트의 꼭짓점이 있는 그래프입니다.
- 집합은 같은 집합의 꼭짓점이 그들 사이에 가장자리를 공유하지 않도록 하는 것입니다.
예시
N =10이면 총 25개의 모서리가 있습니다. -
- 두 세트 모두 5개의 정점을 포함하며 첫 번째 세트의 모든 정점은 두 번째 세트의 다른 모든 정점에 대한 가장자리를 갖습니다.
- 따라서 총 가장자리는 5 * 5 =25가 됩니다.
알고리즘
- 주어진 집합의 모든 꼭짓점이 다른 집합의 다른 모든 꼭짓점에 대한 간선을 가질 때 가장자리 수는 최대가 됩니다. 즉, edge =m * n 여기서 m과 n은 두 집합의 가장자리 수입니다.
- 가장자리의 수를 최대화하려면 m이 가능한 n과 같거나 가까워야 합니다.
- 따라서 최대 모서리 수는 다음 공식으로 계산할 수 있습니다. -
(n * n) / 4
예시
#include <bits/stdc++.h>
using namespace std;
int getMaxEdges(int n) {
return floor((n * n) / 4);
}
int main() {
int n = 7;
cout << "Maximum edges = " << getMaxEdges(n) << endl;
return 0;
} 출력
위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -
Maximum edges = 12