노드와 에지를 포함하는 그래프가 제공됩니다. 목표는 그래프의 모서리에 연결된 가능한 노드의 최대 수를 찾는 것입니다. 우리는 그렇지 않다는 것을 알고 있습니다. 노드의 수는 항상 완전한 그래프의 간선 수보다 작거나 같습니다.
노드의 수가 n이고 n(n-1)/2개의 에지가 있는 완전한 그래프를 만들어 이를 수행합니다.
edge=n(n-1)/2 (여기서 n은 노드)
2*에지=n(n-1). 일단 n(n-1)> 아니오. 가장자리의 다음 추가 노드가 있습니다. 따라서 i=1에서 i=n까지 반복합니다.
i(i-1)>2*에지까지. 결과로 n-i를 반환합니다.
예를 들어 이해합시다 -
입력 − 노드=5, 가장자리=2
출력 − 그래프에서 에지의 일부가 아닌 노드 수를 최대화합니다. − 2
설명 -
2개의 에지는 최소 3개의 노드와 최대 4개의 노드를 가질 수 있습니다.
3개 노드의 경우 가장자리가 없는 최대 왼쪽 노드=2
입력 − 노드=2, 가장자리=1
출력 − 그래프에서 에지의 일부가 아닌 노드 수를 최대화합니다. − 0
설명 -
에지를 만들기 위해서는 최소 2개의 노드가 필요합니다. 이 경우 둘 다 사용됩니다. 노드가 없습니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
사용 가능한 데이터에 대해 두 개의 가변 노드와 간선을 사용합니다.
-
함수 maximum(int node, int edge)은 no를 취합니다. 노드와 에지의 매개변수로 그래프의 에지에 속하지 않는 최대 노드 수를 반환합니다.
-
변수 i, temp 및 max를 사용합니다.
-
i=0에서 i<=nodes
까지 루프 시작 -
temp=i*(i-1)
계산 -
변수 합계를 2*에지로 계산
-
온도가 합계보다 높을 때마다 FOR
-
max=nodes-i
로 최대 계산 -
결과를 최대값으로 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int maximum(int nodes, int edges){
int i, temp = 0, max;
for (i = 0; i <= nodes; i++){
temp = i * (i - 1);
int total = 2* edges;
if (temp >= total){
break;
}
}
max = nodes - i;
return max;
}
int main(){
int nodes = 10;
int edges = 5;
cout<<"Maximize number of nodes which are not part of any edge in a Graph are:"<<maximum(nodes, edges) << endl;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Maximize number of nodes which are not part of any edge in a Graph are: 6