Today I have done leetcode's November LeetCoding Challenge with cpp.

November LeetCoding Challenge 6

Description

Power Grid Maintenance

You are given an integer c representing c power stations, each with a unique identifier id from 1 to c (1‑based indexing).

These stations are interconnected via n bidirectional cables, represented by a 2D array connections, where each element connections[i] = [ui, vi] indicates a connection between station ui and station vi. Stations that are directly or indirectly connected form a power grid.

Initially, all stations are online (operational).

You are also given a 2D array queries, where each query is one of the following two types:

• [1, x]: A maintenance check is requested for station x. If station x is online, it resolves the check by itself. If station x is offline, the check is resolved by the operational station with the smallest id in the same power grid as x. If no operational station exists in that grid, return -1.

• [2, x]: Station x goes offline (i.e., it becomes non-operational).

Return an array of integers representing the results of each query of type [1, x] in the order they appear.

Note: The power grid preserves its structure; an offline (non‑operational) node remains part of its grid and taking it offline does not alter connectivity.

Example 1:

Example 2:

Constraints:

• 1 <= c <= 105
• 0 <= n == connections.length <= min(105, c * (c - 1) / 2)
• connections[i].length == 2
• 1 <= ui, vi <= c
• ui != vi
• 1 <= queries.length <= 2 * 105
• queries[i].length == 2
• queries[i][0] is either 1 or 2.
• 1 <= queries[i][1] <= c

Solution

template<typename T>
std::ostream& operator<<(std::ostream &out, const std::vector<T> &v) {
  if(v.size() == 0) {
    out << "[]" << std::endl;
    return out;
  }
  out << '[' << v[0];
  for(int i = 1; i < v.size(); ++i) {
    out << ", " << v[i];
  }
  out << ']';
  return out;
}
struct UnionSet {
  vector<int> parent;
public:
  UnionSet(int size): parent(size) {
    iota(parent.begin(), parent.end(), 0);
  }

  int find(int x) {
    while(parent[x] != x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return parent[x];
  }

  void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if(x != y) parent[y] = x;
  }
  void print() {
    cout << parent << endl;
  }
};
class Solution {
public:
  vector<int> processQueries(int c, vector<vector<int>>& connections, vector<vector<int>>& queries) {
    UnionSet us(c + 1);
    for(const auto &con : connections) {
      us.merge(con[0], con[1]);
    }

    vector<int> next(c + 1);
    vector<int> min(c + 1);
    vector<int> last(c + 1);
    for(int i = 1; i <= c; ++i) {
      int r = us.find(i);
      if(!min[r]) {
        min[r] = i;
      } else {
        next[last[r]] = i;
      }
      last[r] = i;
    }
    // us.print();
    // cout << next << ' ' << min << ' ' << last << endl;

    vector<bool> offline(c + 1, false);
    vector<int> answer;
    answer.reserve(queries.size());

    for(const auto &q : queries) {
      int op = q[0];
      int x = q[1];
      if(op == 1) {
        if(!offline[x]) {
          answer.push_back(x);
        } else {
          int r = us.find(x);
          answer.push_back(min[r] ? min[r] : -1);
        }
      } else {
        if(!offline[x]) {
          offline[x] = true;
          int r = us.find(x);
          if(min[r] == x) {
            int y = next[x];
            while(y && offline[y]) y = next[y];
            min[r] = y ? y : 0;
          }
        }
      }
    }
    return answer;
  }
};

// Accepted
// 671/671 cases passed (28 ms)
// Your runtime beats 98.59 % of cpp submissions
// Your memory usage beats 99.6 % of cpp submissions (292.9 MB)