Phân vùng có thể có trong C ++

Giả sử chúng ta có một tập hợp N người (họ được đánh số 1, 2, ..., N), chúng ta muốn chia mọi người thành hai nhóm con có kích thước bất kỳ. Bây giờ mỗi người có thể không thích một số người khác, và họ không nên đi vào cùng một nhóm. Vì vậy, nếu dislikes [i] =[a, b], nó chỉ ra rằng không được phép xếp những người được đánh số a và b vào cùng một nhóm. Chúng tôi phải tìm xem có thể chia mọi người thành hai nhóm theo cách này không.

Vì vậy, nếu đầu vào là N =4 và không thích =[[1,2], [1,3], [2,4]], đầu ra sẽ là true, nhóm sẽ là [1,4] và [2 , 3].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một mảng các tập hợp được gọi là nhóm, sẽ có hai nhóm

• Tạo một phương thức gọi là dfs (), phương thức này sẽ lấy nút, một đồ thị mảng và x

• aux:=1 - x

• nếu nhóm [aux] có nút, thì trả về false

• chèn nút vào nhóm [x]

• cho tôi trong phạm vi từ 0 đến kích thước của biểu đồ [node] - 1

  • u:=graph [node, i]

  • nếu các nhóm [aux] không có u và dfs (u, graph, aux) là false, thì trả về false

• nếu không thì trả về true

• Từ phương thức chính, thực hiện như sau -

• tạo một mảng được gọi là đồ thị có kích thước [N + 1]

• đối với tôi trong phạm vi từ 0 đến kích thước không thích - 1

  • u:=dislikes [i, 0], v:=dislikes [i, 1]

  • chèn v vào biểu đồ [u] và chèn u vào biểu đồ [v]

• cho tôi trong phạm vi từ 1 đến N

  • nếu nhóm [0] không chứa i và nhóm [1] không có i, thì

    • nếu dfs (i, graph, 0) là false, thì trả về false

• trả về true.

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Đầu ra

true