मान लीजिए हमारे पास एक निर्देशित ग्राफ G का आसन्नता मैट्रिक्स है। जब तक ग्राफ खाली नहीं हो जाता, हम निम्नलिखित ऑपरेशन को दोहराते हैं: G से एक शीर्ष चुनें, फिर उस शीर्ष और उन सभी शीर्षों को मिटा दें जो उस शीर्ष से कुछ किनारों का अनुसरण करके पहुंच योग्य हैं। एक शीर्ष को मिटाने से उससे जुड़े किनारे भी मिट जाएंगे। हमें ऑपरेशन किए जाने की अपेक्षित संख्या ढूंढनी है।
उदाहरण के लिए, यदि इनपुट जैसा है:
तो आउटपुट 1.6667 होगा, क्योंकि प्रारंभ में शीर्ष A चुनें, सभी शीर्ष हटाएं, यदि हम शीर्ष B चुनते हैं, तो B और C हटाएं, और दूसरे ऑपरेशन में A को चुनकर हटाएं, इसी तरह C को चुनने पर भी 2 ऑपरेशन लगते हैं। तो औसत (1+2+2)/3 = 1.6667 है।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
n := G का आकार i := 0 से n-1 तक, करें: G[i, i] := 1 k := 0 से n-1 तक, करें: i := 0 से n-1 तक, करें: j := 0 से n-1 तक, करें: यदि G[i, k] शून्येतर है और G[k, j] शून्येतर है, तो: G[i, j] := 1 ans := 0 i := 0 से n-1 तक, करें: k := 0 j := 0 से n-1 तक, करें: यदि G[j, i] शून्येतर है, तो: k बढ़ाएं ans := ans + 1.0 / k 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
