Problem statement

A power network has c stations numbered 1 to c. The bidirectional cables connections[i] = [u, v] join station u to station v; stations that can reach each other through cables form one power grid. At the start every station is online.

Process queries in order:

• [1, x] — a maintenance check is sent to station x. If x is online, it handles the check itself and the answer is x. Otherwise the answer is the smallest id of an online station in the same power grid as x, or -1 if that grid has no online station left.
• [2, x] — station x goes offline for good. A station that is offline still belongs to its grid: cables are never cut, so it keeps connecting the stations around it.

Return the answers to the [1, x] queries, in the order they were asked.

Example 1

Input: c = 5, connections = [[1,2],[2,3],[4,5]], queries = [[1,2],[2,1],[1,1],[2,4],[1,4],[2,5],[1,5]]
Output: [2,2,5,-1]
Explanation: Grids are {1,2,3} and {4,5}. Station 2 is online. After 1 goes offline, its grid's smallest online station is 2. After 4 goes offline, its grid answers with 5; once 5 is offline too, the grid answers -1.

Example 2

Input: c = 3, connections = [], queries = [[1,1],[2,1],[1,1]]
Output: [1,-1]
Explanation: Without cables every station is a grid of its own.

Example 3

Input: c = 4, connections = [[1,2],[2,3],[3,4]], queries = [[2,2],[1,3],[2,1],[1,2]]
Output: [3,3]
Explanation: Offline station 2 still links 1 to 3, so the grid stays {1,2,3,4}.

Constraints

• 1 <= c <= 10^5
• 0 <= connections.length <= min(10^5, c * (c - 1) / 2)
• connections[i].length == 2
• 1 <= u, v <= c, u != v
• all connections are distinct
• 1 <= queries.length <= 2 * 10^5
• queries[i].length == 2
• queries[i][0] is 1 or 2
• 1 <= queries[i][1] <= c

Hints for Power Grid Maintenance

1. Hint 1

   Cables never disappear, so the grids are fixed from the start — only which stations are online changes.

2. Hint 2

   Find the grids once with union-find (or a DFS) and list each grid's stations in increasing order.

3. Hint 3

   A station never comes back online, so each grid only needs a pointer into its sorted list that moves forward past offline stations.

How to solve Power Grid Maintenance

The grid structure is static and stations only ever switch off, so each grid's answer is the first online entry of its sorted member list — a pointer that only moves forward finds it in amortised constant time.

Approach

1. Union every cable's endpoints in a disjoint-set forest, then record root[s] for every station.
2. Walk the stations 1..c in increasing order and append each to its root's list; every list comes out sorted.
3. Keep ptr[root], initially 0, and an online flag per station.
4. For [2, x], clear online[x].
5. For [1, x]: if x is online answer x; otherwise advance ptr[root[x]] past offline stations and answer the station it rests on, or -1 if it ran off the end.

Why it works

An offline station never returns, so a station the pointer skipped can never be the answer again; the first online station in a sorted list is exactly the smallest online id in that grid.

Complexity

• Time — O((c + n) α(c) + q) — every pointer moves at most c steps in total
• Space — O(c)

Pitfalls

• Going offline does not split a grid — do not remove the station's cables.
• Answer x itself whenever it is online, even if a smaller online station exists in its grid.
• A [2, x] on a station that is already offline changes nothing.

Reference solution

Python

from typing import List

def processQueries(c: int, connections: List[List[int]], queries: List[List[int]]) -> List[int]:
    parent = list(range(c + 1))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in connections:
        a, b = find(u), find(v)
        if a != b:
            parent[a] = b
    root = [find(s) for s in range(c + 1)]
    members = [[] for _ in range(c + 1)]
    for s in range(1, c + 1):
        members[root[s]].append(s)  # increasing ids, so each list is sorted
    ptr = [0] * (c + 1)
    online = [True] * (c + 1)
    res = []
    for t, x in queries:
        if t == 2:
            online[x] = False
        elif online[x]:
            res.append(x)
        else:
            r = root[x]
            lst = members[r]
            p = ptr[r]
            while p < len(lst) and not online[lst[p]]:
                p += 1
            ptr[r] = p
            res.append(lst[p] if p < len(lst) else -1)
    return res

Java

static int pgFind(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

public static int[] processQueries(int c, int[][] connections, int[][] queries) {
    int[] parent = new int[c + 1];
    for (int i = 0; i <= c; i++) parent[i] = i;
    for (int[] e : connections) {
        int a = pgFind(parent, e[0]), b = pgFind(parent, e[1]);
        if (a != b) parent[a] = b;
    }
    int[] root = new int[c + 1];
    List<List<Integer>> members = new ArrayList<>();
    for (int s = 0; s <= c; s++) {
        root[s] = pgFind(parent, s);
        members.add(new ArrayList<>());
    }
    for (int s = 1; s <= c; s++) members.get(root[s]).add(s);
    int[] ptr = new int[c + 1];
    boolean[] offline = new boolean[c + 1];
    List<Integer> res = new ArrayList<>();
    for (int[] q : queries) {
        int x = q[1];
        if (q[0] == 2) { offline[x] = true; continue; }
        if (!offline[x]) { res.add(x); continue; }
        int r = root[x];
        List<Integer> list = members.get(r);
        int p = ptr[r];
        while (p < list.size() && offline[list.get(p)]) p++;
        ptr[r] = p;
        res.add(p < list.size() ? list.get(p) : -1);
    }
    int[] out = new int[res.size()];
    for (int i = 0; i < out.length; i++) out[i] = res.get(i);
    return out;
}

C++

static int pgFind(vector<int>& parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

vector<int> processQueries(int c, vector<vector<int>>& connections, vector<vector<int>>& queries) {
    vector<int> parent(c + 1);
    for (int i = 0; i <= c; i++) parent[i] = i;
    for (auto& e : connections) {
        int a = pgFind(parent, e[0]), b = pgFind(parent, e[1]);
        if (a != b) parent[a] = b;
    }
    vector<int> root(c + 1);
    vector<vector<int>> members(c + 1);
    for (int s = 0; s <= c; s++) root[s] = pgFind(parent, s);
    for (int s = 1; s <= c; s++) members[root[s]].push_back(s);
    vector<int> ptr(c + 1, 0);
    vector<bool> offline(c + 1, false);
    vector<int> res;
    for (auto& q : queries) {
        int x = q[1];
        if (q[0] == 2) { offline[x] = true; continue; }
        if (!offline[x]) { res.push_back(x); continue; }
        int r = root[x];
        vector<int>& list = members[r];
        int p = ptr[r];
        while (p < (int) list.size() && offline[list[p]]) p++;
        ptr[r] = p;
        res.push_back(p < (int) list.size() ? list[p] : -1);
    }
    return res;
}

JavaScript

var processQueries = function(c, connections, queries) {
    var parent = [];
    for (var i = 0; i <= c; i++) parent.push(i);
    var find = function(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    for (var e = 0; e < connections.length; e++) {
        var a = find(connections[e][0]), b = find(connections[e][1]);
        if (a !== b) parent[a] = b;
    }
    var root = [], members = [], ptr = [], online = [];
    for (var s = 0; s <= c; s++) {
        root.push(find(s));
        members.push([]);
        ptr.push(0);
        online.push(true);
    }
    for (var st = 1; st <= c; st++) members[root[st]].push(st);
    var res = [];
    for (var q = 0; q < queries.length; q++) {
        var t = queries[q][0], x = queries[q][1];
        if (t === 2) { online[x] = false; continue; }
        if (online[x]) { res.push(x); continue; }
        var r = root[x], list = members[r], p = ptr[r];
        while (p < list.length && !online[list[p]]) p++;
        ptr[r] = p;
        res.push(p < list.length ? list[p] : -1);
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium