C++ . में संभावित द्विभाजन

मान लीजिए कि हमारे पास N लोगों का एक समूह है (उनकी संख्या 1, 2, ..., N है), हम सभी को किसी भी आकार के दो उपसमूहों में विभाजित करना चाहेंगे। अब प्रत्येक व्यक्ति कुछ अन्य लोगों को नापसंद कर सकता है, और उन्हें एक ही समूह में नहीं जाना चाहिए। इसलिए, यदि नापसंद [i] =[a, b], तो यह इंगित करता है कि a और b नंबर वाले लोगों को एक ही समूह में रखने की अनुमति नहीं है। हमें यह पता लगाना होगा कि क्या इस तरह सभी को दो समूहों में विभाजित करना संभव है।

तो अगर इनपुट एन =4 और नापसंद =[[1,2], [1,3], [2,4]] जैसा है, तो आउटपुट सही होगा, समूह [1,4] और [2] होगा ,3].

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• समूह नामक सेट की एक सरणी बनाएं, दो समूह होंगे

• dfs() नामक एक विधि बनाएं, यह नोड, एक सरणी ग्राफ और x को लेगा

• औक्स :=1 - x

• अगर समूह [ऑक्स] में नोड है, तो झूठी वापसी करें

• समूहों में नोड डालें[x]

• मैं के लिए 0 से ग्राफ़ के आकार में [नोड] - 1

  • यू:=ग्राफ [नोड, आई]

  • अगर group[aux] में कोई u नहीं है और dfs(u, graph, aux) गलत है, तो गलत रिटर्न करें

• अन्यथा सही लौटें

• मुख्य विधि से निम्न कार्य करें -

• आकार का ग्राफ़ नामक एक सरणी बनाएं [N + 1]

• मेरे लिए 0 से लेकर नापसंद के आकार तक - 1

  • यू:=नापसंद [i, 0], वी:=नापसंद [i, 1]

  • ग्राफ़ में v डालें[u] और u को ग्राफ़ में डालें[v]

• 1 से एन तक के लिए मैं

  • अगर समूह [0] में मैं नहीं है और समूह [1] में मैं नहीं है, तो

    • अगर dfs(i, graph, 0) गलत है, तो गलत रिटर्न करें

• सच लौटें।

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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;
   }
};
main(){
   vector<vector<int>> v = {{1,2},{1,3},{2,4}};
   Solution ob;
   cout << (ob.possibleBipartition(4, v));
}

इनपुट

4
[[1,2],[1,3],[2,4]]

आउटपुट

true