การแบ่งสองส่วนที่เป็นไปได้ใน C ++

สมมติว่าเรามีกลุ่มคน N (มีหมายเลข 1, 2, ..., N) เราอยากจะแบ่งทุกคนออกเป็นสองกลุ่มย่อยทุกขนาด ตอนนี้แต่ละคนอาจจะไม่ชอบคนอื่นบ้างและไม่ควรไปอยู่กลุ่มเดียวกัน ดังนั้น ถ้า dislikes[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 :=กราฟ[โหนด ผม]

  • หากกลุ่ม[aux] ไม่มี u และ dfs(u, graph, aux) เป็นเท็จ ให้คืนค่าเท็จ

• มิฉะนั้นคืนค่าเป็น true

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• สร้างอาร์เรย์ที่เรียกว่ากราฟขนาด [N + 1]

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของไม่ชอบ - 1

  • u :=ไม่ชอบ[i, 0], v :=ไม่ชอบ[i, 1]

  • แทรก v ลงใน graph[u] และ แทรก u ลงใน graph[v]

• สำหรับฉันอยู่ในช่วง 1 ถึง N

  • หากกลุ่ม[0] ไม่มี i และกลุ่ม[1] ไม่มี i ดังนั้น

    • ถ้า 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