ধরুন আমাদের কাছে N লোকের একটি সেট আছে (তাদের সংখ্যা 1, 2, ..., N), আমরা প্রত্যেককে যেকোনো আকারের দুটি উপগোষ্ঠীতে বিভক্ত করতে চাই। এখন প্রতিটি ব্যক্তি অন্য কিছু লোককে অপছন্দ করতে পারে এবং তাদের একই দলে যাওয়া উচিত নয়। সুতরাং, যদি অপছন্দ করেন [i] =[a, b], তাহলে এটি নির্দেশ করে যে a এবং b নম্বরযুক্ত ব্যক্তিদের একই গ্রুপে রাখার অনুমতি নেই। এভাবে সবাইকে দুই ভাগে ভাগ করা সম্ভব কিনা তা আমাদের খুঁজে বের করতে হবে।
সুতরাং যদি ইনপুটটি N =4 এবং অপছন্দ =[[1,2],[1,3],[2,4]] এর মত হয় তবে আউটপুটটি সত্য হবে, গ্রুপটি হবে [1,4] এবং [2] ,3]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
গ্রুপ নামক সেটের একটি অ্যারে তৈরি করুন, সেখানে দুটি গ্রুপ থাকবে
-
dfs() নামে একটি পদ্ধতি তৈরি করুন, এটি নোড, একটি অ্যারে গ্রাফ এবং x
নেবে -
aux :=1 – x
-
যদি গ্রুপ[aux] নোড থাকে, তাহলে মিথ্যা ফেরত দিন
-
গ্রুপে নোড সন্নিবেশ করান [x]
-
আমি 0 থেকে গ্রাফ [নোড] - 1
এর আকারের মধ্যে-
u :=গ্রাফ[নোড, i]
-
যদি গ্রুপ[aux] এর কোনো u না থাকে এবং dfs(u, graph, aux) মিথ্যা হয়, তাহলে মিথ্যা ফেরত দিন
-
-
অন্যথায় সত্য প্রত্যাবর্তন করুন
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
আকারের গ্রাফ নামে একটি অ্যারে তৈরি করুন [N + 1]
-
আমার জন্য 0 থেকে অপছন্দের আকার - 1
-
u :=অপছন্দ[i, 0], v :=অপছন্দ[i, 1]
-
গ্রাফ[u]-এ v সন্নিবেশ করান এবং গ্রাফ[v]
-এ ঢোকান
-
-
আমি 1 থেকে N
রেঞ্জের মধ্যে-
যদি গ্রুপ[0]-এ i না থাকে এবং গ্রুপ[1]-এ i না থাকে, তাহলে
-
যদি dfs(i, গ্রাফ, 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
