একটি গাছে সর্বোচ্চ সংখ্যক প্রান্ত যোগ করতে হবে যাতে এটি 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}

অ্যালগরিদম

• গ্রাফের একটি সাধারণ ডিএফএস বা বিএফএস ট্রাভার্সাল করুন এবং এটি দুটি রঙে রঙ করুন
• রঙ করার সময় দুটি রঙের সাথে রঙিন নোডের সংখ্যার উপর নজর রাখুন। গণনা দুটিকে গণনা_রঙ0 এবং গণনা_রঙ1
হতে দিন
• এখন আমরা জানি যে দ্বিপক্ষীয় গ্রাফের সর্বাধিক প্রান্তগুলি গণনা_রঙ0 x গণনা_রঙ1 হতে পারে
• আমরা জানি যে 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