C++で可能な2分割

N人のセット（1、2、...、Nの番号が付けられている）があるとすると、すべての人を任意のサイズの2つのサブグループに分割します。今、各人は他の人を嫌うかもしれません、そして彼らは同じグループに入るべきではありません。したがって、dislikes [i] =[a、b]の場合、aとbの番号が付けられた人々を同じグループに入れることは許可されていないことを示します。この方法で全員を2つのグループに分割できるかどうかを確認する必要があります。

したがって、入力がN =4で、嫌い=[[1,2]、[1,3]、[2,4]]の場合、出力はtrueになり、グループは[1,4]と[2]になります。 、3]。

これを解決するには、次の手順に従います-

• グループと呼ばれるセットの配列を作成します。2つのグループがあります

• dfs（）というメソッドを作成します。これにより、ノード、配列グラフ、およびx

  が取得されます。

• aux：=1 – x

• groups [aux]にノードがある場合は、falseを返します

• グループにノードを挿入します[x]

• 0からグラフのサイズ[ノード]– 1

  の範囲のiの場合

  • u：=グラフ[ノード、i]

  • groups [aux]にuがなく、dfs（u、graph、aux）がfalseの場合、falseを返します

• それ以外の場合はtrueを返します

• メインの方法から、次のようにします-

• サイズ[N+1]

  のグラフと呼ばれる配列を作成します

• 0から嫌いなもののサイズまでの範囲のiの場合-1

  • u：=嫌い[i、0]、v：=嫌い[i、1]

  • vをgraph[u]に挿入し、uをgraph [v]

    に挿入します

• 1からNの範囲のiの場合

  • groups [0]にiが含まれておらず、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