मान लीजिए हमारे पास N लोगों का एक समूह है (वे 1, 2, ..., N नंबर वाले हैं), हम सभी को किन्हीं दो उपसमूहों में विभाजित करना चाहते हैं। अब प्रत्येक व्यक्ति कुछ अन्य लोगों को नापसंद कर सकता है, और उन्हें एक ही समूह में नहीं जाना चाहिए। इसलिए, यदि dislikes[i] = [a, b], तो यह इंगित करता है कि a और b नंबर वाले लोगों को एक ही समूह में रखने की अनुमति नहीं है। हमें पता लगाना है कि क्या सभी को इस तरह दो समूहों में विभाजित करना संभव है।
उदाहरण के लिए, यदि N = 4 और dislike = [[1,2],[1,3],[2,4]], तो आउटपुट true होगा, समूह [1,4] और [2,3] होंगे।
समाधान दृष्टिकोण
दो समूहों का सेट ऐरे groups बनाएं
DFS विधि: नोड को ग्रुप x में असाइन करें, पड़ोसियों को ग्रुप 1-x में DFS करें
यदि विरोधाभास मिले तो false लौटाएं
ग्राफ बनाएं, प्रत्येक अनविजिटेड नोड से DFS चलाएं
true लौटाएं यदि कोई विरोधाभास नहीं
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
set<int> groups[2];
bool dfs(int node, vector<int> graph[], int x){
int aux = 1 - x;
if(groups[aux].count(node)) return false;
groups[x].insert(node);
for(int i = 0; i < graph[node].size(); i++){
int u = graph[node][i];
if(!groups[aux].count(u) && !dfs(u, graph, aux)) return false;
}
return true;
}
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
vector<int> graph[N + 1];
for(int i = 0; i < dislikes.size(); i++){
int u = dislikes[i][0];
int v = dislikes[i][1];
graph[u].push_back(v);
graph[v].push_back(u);
}
for(int i = 1; i <= N; i++){
if(!groups[0].count(i) && !groups[1].count(i)){
if(!dfs(i, graph, 0)) return false;
}
}
return true;
}
};
int main(){
vector<vector<int>> v = {{1,2},{1,3},{2,4}};
Solution ob;
cout << (ob.possibleBipartition(4, v));
return 0;
}
इनपुट
4 [[1,2],[1,3],[2,4]]
आउटपुट
true
