मान लीजिए कि हमारे पास एक ग्राफ 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
. होगाकदम
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
Define an array dp of size: 210. n := size of matrix fl := 1 ans := 0 for initialize i := 0, when i < n and fl is non-zero, update (increase i by 1), do: fill dp with -1 dp[i] := 0 Define one queue q insert i into q while (q is not empty), do: x := first element of q delete element from q for initialize j := 0, when j < n, update (increase j by 1), do: if matrix[x, j] is same as 1, then: if dp[j] is same as -1, then: dp[j] := dp[x] + 1 insert j into q otherwise when |dp[j] - dp[x]| is not equal to 1, then: fl := 0 for initialize j := 0, when j < n, update (increase j by 1), do: ans := maximum of ans and dp[j] if fl is same as 0, then: return -1 Otherwise return 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
