সমস্ত নোড অপসারণের জন্য প্রয়োজনীয় অপারেশনের প্রত্যাশিত সংখ্যা গণনা করার জন্য C++ প্রোগ্রাম

ধরুন আমাদের কাছে একটি নির্দেশিত গ্রাফ G এর সংলগ্নতা ম্যাট্রিক্স রয়েছে। যতক্ষণ না গ্রাফটি খালি হয়ে যায়, আমরা নিম্নলিখিত ক্রিয়াকলাপটি পুনরাবৃত্তি করছি:G থেকে একটি শীর্ষবিন্দু নির্বাচন করুন, তারপর সেই শীর্ষবিন্দুটি মুছে ফেলুন এবং কিছু প্রান্ত অনুসরণ করে সেই শীর্ষবিন্দু থেকে পৌঁছানো যায় এমন সমস্ত শীর্ষবিন্দু মুছুন। একটি শীর্ষবিন্দু মুছে ফেলার ফলে এটির প্রান্তের ঘটনাও মুছে যাবে। অপারেশনটি কতবার করা হয়েছে তা আমাদের খুঁজে বের করতে হবে

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 1.6667, কারণ প্রাথমিকভাবে vertex A সিলেক্ট করে সমস্ত ভার্টিক্স মুছে ফেলুন, যদি আমরা ভার্টেক্স B সিলেক্ট করি, B এবং C রিমুভ করি এবং দ্বিতীয় অপারেশনে A সিলেক্ট করে এটি রিমুভ করি, একইভাবে C সিলেক্ট করলেও 2টি অপারেশন লাগে। সুতরাং গড় হল (1+2+2)/3 =1.6667।

পদক্ষেপ

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n := size of G
for initialize i := 0, when i < n, update (increase i by 1), do:
   G[i, i] := 1
for initialize k := 0, when k < n, update (increase k by 1), do:
   for initialize i := 0, when i < n, update (increase i by 1), do:
      for initialize j := 0, when j < n, update (increase j by 1), do:
         if G[i, k] is non-zero and G[k, j] is non-zero, then:
            G[i, j] := 1
         ans := 0
      for initialize i := 0, when i < n, update (increase i by 1), do:
         k := 0
      for initialize j := 0, when j < n, update (increase j by 1), do:
         if G[j, i] is non-zero, then:
            (increase k by 1)
         ans := ans + 1.0 / k
return ans

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;

double solve(vector<vector<int>> G){
   int n = G.size();
   for (int i = 0; i < n; ++i)
      G[i][i] = 1;
   for (int k = 0; k < n; ++k)
      for (int i = 0; i < n; ++i)
         for (int j = 0; j < n; ++j)
            if (G[i][k] && G[k][j])
               G[i][j] = 1;
   double ans = 0;
   for (int i = 0; i < n; ++i){
      int k = 0;
      for (int j = 0; j < n; ++j)
         if (G[j][i])
            ++k;
         ans += 1.0 / k;
   }
   return ans;
}
int main(){
   vector<vector<int>> G = { { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 }};
   cout << solve(G) << endl;
}

ইনপুট

{ { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 } }

আউটপুট

1.66667