fork download
copy 
  1. /*
  2.     Problem: Divide People Into Two Friendly Tables
  3.     Company Tag: Media.net OA
  4.  
  5.     Problem Statement:
  6.         We are given N people and M friendship connections.
  7.  
  8.         There are 2 tables.
  9.  
  10.         People sitting at the same table must all be friends with each other.
  11.         So each table must form a clique.
  12.  
  13.         Return true if all people can be divided into at most 2 groups
  14.         such that each group forms a clique.
  15.  
  16.     Constraints:
  17.         1 <= N <= 1000
  18.         0 <= M <= N * (N - 1) / 2
  19.         1 <= friendships[i][0], friendships[i][1] <= N
  20.         No duplicate friendship connections.
  21.  
  22.     Brute Force:
  23.         Try all possible ways to divide people into 2 groups.
  24.  
  25.     Why Brute Force Fails:
  26.         Each person can go to table 1 or table 2.
  27.         Total possibilities = 2^N.
  28.  
  29.     Optimized Idea:
  30.         If two people are not friends, they cannot sit together.
  31.  
  32.         So I create the complement graph:
  33.             Edge exists if two people are NOT friends.
  34.  
  35.         Now each complement edge means:
  36.             These two people must be in different groups.
  37.  
  38.         So the problem becomes:
  39.             Is the complement graph bipartite?
  40.  
  41.     Explanation Block:
  42.         Original problem asks for 2 cliques.
  43.  
  44.         Complement graph converts the problem into 2-coloring:
  45.             - Non-friends must get different colors.
  46.             - If this is possible, answer is true.
  47.             - Otherwise, answer is false.
  48.  
  49.     Dry Run:
  50.         N = 4
  51.  
  52.         friendships:
  53.             1 - 2
  54.             2 - 3
  55.             3 - 4
  56.             4 - 1
  57.  
  58.         Missing friendships:
  59.             1 - 3
  60.             2 - 4
  61.  
  62.         Complement graph is bipartite.
  63.  
  64.         Answer = true
  65.  
  66.     Time Complexity:
  67.         O(N^2)
  68.  
  69.     Space Complexity:
  70.         O(N^2)
  71. */
  72.  
  73. #include <bits/stdc++.h>
  74. using namespace std;
  75.  
  76. bool canDivideIntoTwoFriendlyTables(int n, vector<vector<int>>& friendships) {
  77.     vector<vector<int>> isFriend(n, vector<int>(n, 0));
  78.  
  79.     // Mark direct friendship.
  80.     for (auto& e : friendships) {
  81.         int u = e[0] - 1;
  82.         int v = e[1] - 1;
  83.  
  84.         isFriend[u][v] = 1;
  85.         isFriend[v][u] = 1;
  86.     }
  87.  
  88.     vector<int> color(n, -1);
  89.  
  90.     // Check every component of the complement graph.
  91.     for (int start = 0; start < n; start++) {
  92.         if (color[start] != -1) {
  93.             continue;
  94.         }
  95.  
  96.         queue<int> q;
  97.  
  98.         q.push(start);
  99.         color[start] = 0;
  100.  
  101.         while (!q.empty()) {
  102.             int u = q.front();
  103.             q.pop();
  104.  
  105.             for (int v = 0; v < n; v++) {
  106.                 if (u == v) {
  107.                     continue;
  108.                 }
  109.  
  110.                 // If they are friends, no edge exists in complement graph.
  111.                 if (isFriend[u][v]) {
  112.                     continue;
  113.                 }
  114.  
  115.                 // If they are not friends, they must be in different groups.
  116.                 if (color[v] == -1) {
  117.                     color[v] = color[u] ^ 1;
  118.                     q.push(v);
  119.                 } else if (color[v] == color[u]) {
  120.                     // Same color means they are forced into same table,
  121.                     // but they are not friends.
  122.                     return false;
  123.                 }
  124.             }
  125.         }
  126.     }
  127.  
  128.     return true;
  129. }
  130.  
  131. int main() {
  132.     int n = 4;
  133.  
  134.     vector<vector<int>> friendships = {
  135.         {1, 2},
  136.         {2, 3},
  137.         {3, 4},
  138.         {4, 1}
  139.     };
  140.  
  141.     cout << (canDivideIntoTwoFriendlyTables(n, friendships) ? "true" : "false") << endl;
  142.  
  143.     return 0;
  144. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
true
https://ideone.com/Vkdmma
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!