Chúng ta được đưa ra một đồ thị có chứa các nút và các cạnh. Mục đích là để tìm số lượng tối đa các nút có thể được kết nối với bất kỳ cạnh nào của biểu đồ. Chúng tôi biết rằng không. số nút sẽ luôn nhỏ hơn hoặc bằng số cạnh trong một biểu đồ hoàn chỉnh.
Chúng ta sẽ làm điều này bằng cách cố gắng tạo một đồ thị hoàn chỉnh trong đó số nút là n thì sẽ có n (n-1) / 2 cạnh.
edge =n (n-1) / 2 (ở đây là n cho các nút)
2 * cạnh =n (n-1). Một khi n (n-1)> không. của các cạnh thì chúng ta có thêm các nút. Vì vậy, hãy lặp lại từ i =1 đến i =n.
Cho đến khi i (i-1)> 2 * cạnh. Kết quả là trả về n-i.
Hãy cho chúng tôi hiểu với các ví dụ -
Đầu vào - nút =5, cạnh =2
Đầu ra - Tối đa hóa số lượng các nút không thuộc bất kỳ cạnh nào trong Biểu đồ là - 2
Giải thích -
2 cạnh có thể có tối thiểu 3 nút và tối đa 4 nút.
Đối với 3 nút tối đa các nút bên trái không có cạnh nào =2
Đầu vào - nút =2, cạnh =1
Đầu ra - Tối đa hóa số lượng các nút không thuộc bất kỳ cạnh nào trong Biểu đồ là - 0
Giải thích -
Ít nhất 2 nút được yêu cầu để tạo ra một cạnh. Trong trường hợp này, cả hai đều bị chiếm dụng. Không còn nút nào.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chúng tôi lấy hai nút và cạnh thay đổi cho dữ liệu có sẵn.
-
Hàm tối đa (int node, int edge) không có. các nút và cạnh dưới dạng tham số và trả về số lượng nút tối đa không phải là một phần của bất kỳ cạnh nào trong Biểu đồ
-
Lấy các biến số i, nhiệt độ và giá trị tối đa.
-
Bắt đầu vòng lặp FOR từ i =0 đến i <=nút
-
Tính temp =i * (i-1)
-
Tính tổng biến dưới dạng 2 * cạnh
-
Bất cứ khi nào nhiệt độ trở nên nhiều hơn tổng, hãy phá vỡ FOR
-
Tính toán tối đa là max =node-i
-
Trả về kết quả là giá trị tối đa.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Maximize number of nodes which are not part of any edge in a Graph are: 6