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