C++ में ट्री में जोड़े जा सकने वाले अधिकतम एज ताकि यह द्विभाजित ग्राफ बना रहे

समस्या कथन

एक ट्री हमेशा एक द्विभाजित ग्राफ होता है क्योंकि हम इसे हमेशा दो असंयुक्त सेट में वैकल्पिक स्तरों के साथ विभाजित कर सकते हैं।

दूसरे शब्दों में, हम इसे हमेशा दो रंगों से रंग सकते हैं ताकि वैकल्पिक स्तरों का रंग समान हो। कार्य यह गणना करना है कि ट्री में अधिकतम कितने एज जोड़े जा सकते हैं ताकि यह द्विभाजित ग्राफ बना रहे।

उदाहरण

ट्री एज को शीर्ष जोड़े के रूप में दर्शाया गया है -

{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} हैं

एल्गोरिदम

• ग्राफ का एक साधारण DFS या BFS ट्रैवर्सल करें और इसे दो रंगों से रंगें
• रंगते समय दोनों रंगों से रंगे नोड्स की गिनती भी ट्रैक करें। मान लें कि दो गिनती 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 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 graph[], int n) {
    dfs(graph, 1, 0, 0);
    return count_color[0] * count_color[1] - (n - 1);
}

int main() {
    int n = 5;
    vector 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