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

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

উদাহরণ

যদি ইনপুট গ্রাফটি দেওয়া হয় (চিত্রে দেখানো হয়েছে), তবে আউটপুট হবে 1.6667। কারণ:
- প্রথমে ভার্টেক্স A নির্বাচন করলে সব মুছে যায় (১ অপারেশন)
- B নির্বাচন করলে B এবং C মুছে যায়, দ্বিতীয় অপারেশনে A মুছে ফেলতে হয় (২ অপারেশন)
- C নির্বাচন করলেও ২ অপারেশন লাগে
গড় = (১+২+২)/৩ = ১.৬৬৬৭

সমাধানের ধাপসমূহ

n := G এর আকার
for i := 0 থেকে n-1:
    G[i][i] := 1
for k := 0 থেকে n-1:
    for i := 0 থেকে n-1:
        for j := 0 থেকে n-1:
            যদি G[i][k] এবং G[k][j] উভয়ই নন-জিরো:
                G[i][j] := 1
ans := 0
for i := 0 থেকে n-1:
    k := 0
    for j := 0 থেকে n-1:
        যদি G[j][i] নন-জিরো:
            k বাড়ান
    ans := ans + 1.0 / k
ans রিটার্ন করুন

C++ বাস্তবায়ন

#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