समस्या कथन
एक पेड़ हमेशा एक द्विदलीय ग्राफ होता है क्योंकि हम हमेशा वैकल्पिक स्तरों के साथ दो अलग-अलग सेटों में टूट सकते हैं।
दूसरे शब्दों में, हम इसे हमेशा दो रंगों से रंगते हैं जैसे कि वैकल्पिक स्तरों का रंग समान हो। कार्य अधिकतम संख्या की गणना करना है। किनारों को पेड़ में जोड़ा जा सकता है ताकि यह द्विदलीय ग्राफ बना रहे।
उदाहरण
पेड़ के किनारों को शीर्ष जोड़े में निम्नानुसार दर्शाया गया है -
{1, 2}
{1, 3}
{2}, 4}
{3, 5} तो हमें इसे द्विदलीय ग्राफ रखने के लिए 2 और किनारों की आवश्यकता है
- रंगीन ग्राफ में दो अलग-अलग सेटों से ग्राफ {1, 4, 5} और {2, 3}। चूंकि, 1 2 और 3 दोनों से जुड़ा है
- हमारे पास 4 और 5 किनारे बचे हैं क्योंकि 4 पहले से ही 2 और 5 से 3 से जुड़ा है। केवल शेष विकल्प {4, 3} और {5, 2} है।
एल्गोरिदम
- ग्राफ का एक साधारण डीएफएस या बीएफएस ट्रैवर्सल करें और इसे दो रंगों से रंग दें
- रंग लगाते समय दो रंगों से रंगे नोड्स की संख्या पर भी नज़र रखें। दो गणनाओं को count_color0 और count_color1 होने दें
- अब हम जानते हैं कि एक द्विदलीय ग्राफ़ के अधिकतम किनारे हो सकते हैं count_color0 x count_color1
- हम यह भी जानते हैं कि n नोड्स वाले पेड़ में n-1 किनारे होते हैं
- तो हमारा उत्तर है count_color0 x count_color1 - (n-1)
उदाहरण
#include <bits/stdc++.h>
using namespace std;
long long count_color[2];
void dfs(vector<int> graph[], int node, int parent, int color) {
++count_color[color];
for (int i = 0; i < graph[node].size(); ++i) {
if (graph[node][i] != parent) {
dfs(graph, graph[node][i], node, !color);
}
}
}
int getMaxEdges(vector<int> graph[], int n) {
dfs(graph, 1, 0, 0);
return count_color[0] * count_color[1] - (n - 1);
}
int main() {
int n = 5;
vector<int> graph[n + 1];
graph[1].push_back(2);
graph[1].push_back(3);
graph[2].push_back(4);
graph[3].push_back(5);
cout << "Maximum edges = " << getMaxEdges(graph, n) << endl;
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -
Maximum edges = 2