fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5.     Problem: House Cleaning
  6.  
  7.     You are given N houses on a 2D grid.
  8.     Each house is represented by a coordinate (x, y).
  9.  
  10.     A cleaning employee can be assigned in exactly one of two ways:
  11.  
  12.     1) Row cleaning:
  13.        The employee cleans all houses having the same x-coordinate.
  14.  
  15.     2) Column cleaning:
  16.        The employee cleans all houses having the same y-coordinate.
  17.  
  18.     Every house must be cleaned by at least one employee.
  19.  
  20.     Your task is to return the minimum number of employees needed.
  21.  
  22.     ------------------------------------------------------------
  23.  
  24.     Function:
  25.     int houseCleaning(int input1, vector<vector<int>> input2)
  26.  
  27.     Parameters:
  28.     - input1 = number of houses
  29.     - input2[i] = {x, y}, the coordinates of the i-th house
  30.  
  31.     A house is considered covered if:
  32.     - its row is chosen, or
  33.     - its column is chosen
  34.  
  35.     ------------------------------------------------------------
  36.  
  37.     Example 1:
  38.     N = 3
  39.     houses = {{0,1}, {0,2}, {1,2}}
  40.  
  41.     One optimal choice:
  42.     - choose row 0  -> covers (0,1), (0,2)
  43.     - choose col 2  -> covers (0,2), (1,2)
  44.  
  45.     So answer = 2
  46.  
  47.     ------------------------------------------------------------
  48.  
  49.     Example 2:
  50.     N = 4
  51.     houses = {{0,0}, {0,1}, {1,0}, {1,1}}
  52.  
  53.     We can choose:
  54.     - row 0 and row 1
  55.     or
  56.     - col 0 and col 1
  57.  
  58.     So answer = 2
  59.  
  60.     ------------------------------------------------------------
  61.  
  62.     Main idea:
  63.  
  64.     Think of this as a bipartite graph.
  65.  
  66.     - Every distinct row becomes a node on the left side
  67.     - Every distinct column becomes a node on the right side
  68.     - Every house (x, y) becomes an edge between row x and column y
  69.  
  70.     Now the problem becomes:
  71.  
  72.     "Choose the minimum number of row/column nodes
  73.      so that every edge is covered."
  74.  
  75.     That is exactly the Minimum Vertex Cover problem
  76.     in a Bipartite Graph.
  77.  
  78.     By Kőnig’s theorem:
  79.     Minimum Vertex Cover size = Maximum Matching size
  80.  
  81.     So we only need to find the maximum matching.
  82.  
  83.     This code uses the Hopcroft-Karp algorithm for that.
  84.  
  85.     Time Complexity:
  86.     O(E * sqrt(V)) in practice for bipartite matching
  87.  
  88.     where:
  89.     - V = number of distinct rows + number of distinct columns
  90.     - E = number of houses
  91. */
  92.  
  93. class Solution {
  94.     // graph[u] = list of column nodes connected to row node u
  95.     vector<vector<int>> graph;
  96.  
  97.     // level[u] is used in BFS phase of Hopcroft-Karp
  98.     vector<int> level;
  99.  
  100.     // leftMatch[u] = which right-side node is matched with left node u
  101.     // rightMatch[v] = which left-side node is matched with right node v
  102.     // -1 means unmatched
  103.     vector<int> leftMatch, rightMatch;
  104.  
  105.     // BFS builds layers and checks whether any augmenting path exists
  106.     bool bfs(int leftSize) {
  107.         queue<int> q;
  108.  
  109.         for (int u = 0; u < leftSize; u++) {
  110.             if (leftMatch[u] == -1) {
  111.                 level[u] = 0;
  112.                 q.push(u);
  113.             } else {
  114.                 level[u] = -1;
  115.             }
  116.         }
  117.  
  118.         bool foundAugmentingPath = false;
  119.  
  120.         while (!q.empty()) {
  121.             int u = q.front();
  122.             q.pop();
  123.  
  124.             for (int v : graph[u]) {
  125.                 int matchedLeft = rightMatch[v];
  126.  
  127.                 // If this right node is free, we found a possible augmenting path
  128.                 if (matchedLeft == -1) {
  129.                     foundAugmentingPath = true;
  130.                 }
  131.                 // Otherwise continue through the matched left node
  132.                 else if (level[matchedLeft] == -1) {
  133.                     level[matchedLeft] = level[u] + 1;
  134.                     q.push(matchedLeft);
  135.                 }
  136.             }
  137.         }
  138.  
  139.         return foundAugmentingPath;
  140.     }
  141.  
  142.     // DFS tries to actually use one augmenting path starting from u
  143.     bool dfs(int u) {
  144.         for (int v : graph[u]) {
  145.             int matchedLeft = rightMatch[v];
  146.  
  147.             // If v is free, match it directly
  148.             // Otherwise try to reroute the current matched node deeper
  149.             if (matchedLeft == -1 || (level[matchedLeft] == level[u] + 1 && dfs(matchedLeft))) {
  150.                 leftMatch[u] = v;
  151.                 rightMatch[v] = u;
  152.                 return true;
  153.             }
  154.         }
  155.  
  156.         // No useful path from this node in current BFS layering
  157.         level[u] = -1;
  158.         return false;
  159.     }
  160.  
  161. public:
  162.     int houseCleaning(int input1, vector<vector<int>> input2) {
  163.         // Compress actual row values and column values into 0-based ids
  164.         unordered_map<int, int> rowId, colId;
  165.  
  166.         int rowCount = 0, colCount = 0;
  167.  
  168.         for (auto &house : input2) {
  169.             int x = house[0];
  170.             int y = house[1];
  171.  
  172.             if (!rowId.count(x)) rowId[x] = rowCount++;
  173.             if (!colId.count(y)) colId[y] = colCount++;
  174.         }
  175.  
  176.         // Build bipartite graph:
  177.         // row x is connected to column y if house (x, y) exists
  178.         graph.assign(rowCount, {});
  179.  
  180.         for (auto &house : input2) {
  181.             int u = rowId[house[0]];
  182.             int v = colId[house[1]];
  183.             graph[u].push_back(v);
  184.         }
  185.  
  186.         // Remove duplicate edges in case same coordinate appears multiple times
  187.         for (int u = 0; u < rowCount; u++) {
  188.             sort(graph[u].begin(), graph[u].end());
  189.             graph[u].erase(unique(graph[u].begin(), graph[u].end()), graph[u].end());
  190.         }
  191.  
  192.         // Initially no matches
  193.         leftMatch.assign(rowCount, -1);
  194.         rightMatch.assign(colCount, -1);
  195.         level.assign(rowCount, 0);
  196.  
  197.         int maxMatching = 0;
  198.  
  199.         // Standard Hopcroft-Karp loop
  200.         while (bfs(rowCount)) {
  201.             for (int u = 0; u < rowCount; u++) {
  202.                 if (leftMatch[u] == -1 && dfs(u)) {
  203.                     maxMatching++;
  204.                 }
  205.             }
  206.         }
  207.  
  208.         /*
  209.             By Kőnig’s theorem:
  210.             minimum vertex cover size = maximum matching size
  211.  
  212.             That is exactly the minimum number of employees needed.
  213.         */
  214.         return maxMatching;
  215.     }
  216. };
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout 
Standard output is empty
https://ideone.com/s6TtR5
language:
C++14 (gcc 8.3)
created:
4 days 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!