मान लीजिए हमारे पास एक ग्राफ G का आसन्नता मैट्रिक्स है। हमें जांचना है कि क्या हम शीर्षों को गैर-खाली सेट V1, ... Vk में विभाजित कर सकते हैं, जैसे कि: प्रत्येक किनारा दो शीर्षों को जोड़ता है जो दो आसन्न सेट से संबंधित हैं। यदि उत्तर हां है, तो हमें ऐसे विभाजन में सेट k का अधिकतम संभव मान ढूंढना है।
उदाहरण के लिए, यदि इनपुट है:
| 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 |
तो आउटपुट 4 होगा
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
आकार 210 का एक ऐरे dp परिभाषित करें n := मैट्रिक्स का आकार fl := 1 ans := 0 i := 0 से n-1 तक और fl शून्येतर होने तक, करें: dp को -1 से भरें dp[i] := 0 एक कतार q परिभाषित करें i को q में डालें जब तक (q खाली नहीं है), करें: x := q का पहला तत्व q से तत्व हटाएं j := 0 से n-1 तक, करें: यदि matrix[x, j], 1 के बराबर है, तो: यदि dp[j], -1 के बराबर है, तो: dp[j] := dp[x] + 1 j को q में डालें अन्यथा जब |dp[j] - dp[x]|, 1 के बराबर नहीं है, तो: fl := 0 j := 0 से n-1 तक, करें: ans := ans और dp[j] का अधिकतम यदि fl, 0 के बराबर है, तो: -1 वापस करें अन्यथा ans + 1 वापस करें
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; int solve(vector<vector<int>> matrix){ int dp[210]; int n = matrix.size(); int fl = 1; int ans = 0; for (int i = 0; i < n && fl; i++){ memset(dp, -1, sizeof(dp)); dp[i] = 0; queue<int> q; q.push(i); while (!q.empty()){ int x = q.front(); q.pop(); for (int j = 0; j < n; j++){ if (matrix[x][j] == 1){ if (dp[j] == -1){ dp[j] = dp[x] + 1; q.push(j); } else if (abs(dp[j] - dp[x]) != 1) fl = 0; } } } for (int j = 0; j < n; j++) ans = max(ans, dp[j]); } if (fl == 0){ return -1; }else{ return ans + 1; } } int main(){ vector<vector<int>> matrix = { { 0, 1, 0, 1, 1, 0 }, { 1, 0, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0 }, { 1, 0, 1, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0, 0 } }; cout << solve(matrix) << endl; } इनपुट
{ { 0, 1, 0, 1, 1, 0 }, { 1, 0, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0 }, { 1, 0, 1, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0, 0 } } आउटपुट
4