सभी नोड हटाने के लिए आवश्यक संचालन की अपेक्षित संख्या की गणना करने के लिए सी ++ प्रोग्राम

मान लीजिए कि हमारे पास एक निर्देशित ग्राफ़ G का आसन्न मैट्रिक्स है। जब तक ग्राफ़ खाली नहीं हो जाता, हम निम्नलिखित ऑपरेशन दोहरा रहे हैं:G से एक शीर्ष का चयन करें, फिर उस शीर्ष और सभी शीर्षों को मिटा दें जो कुछ किनारों का अनुसरण करके उस शीर्ष से पहुंच योग्य हैं। एक शीर्ष को मिटाने से किनारों की घटना भी मिट जाएगी। हमें ऑपरेशन किए जाने की अपेक्षित संख्या का पता लगाना होगा

तो, अगर इनपुट पसंद है

तो आउटपुट 1.6667 होगा, क्योंकि शुरू में वर्टेक्स ए का चयन करें, सभी कोने हटा दें, अगर हम वर्टेक्स बी का चयन करते हैं, बी और सी को हटाते हैं, और दूसरे ऑपरेशन में इसे हटाने के लिए ए का चयन करें, इसी तरह सी का चयन करके भी 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