1#include <vector>
2#include <algorithm>
3#include <numeric>
4
5class UnionFind {
6public:
7    std::vector<int> parent, rank;
8    UnionFind(int size) : parent(size), rank(size, 1) {
9        std::iota(parent.begin(), parent.end(), 0);
10    }
11    int find(int u) {
12        if (u != parent[u])
13            parent[u] = find(parent[u]);
14        return parent[u];
15    }
16    void union_sets(int u, int v) {
17        int rootU = find(u);
18        int rootV = find(v);
19        if (rootU != rootV) {
20            if (rank[rootU] > rank[rootV])
21                parent[rootV] = rootU;
22            else if (rank[rootU] < rank[rootV])
23                parent[rootU] = rootV;
24            else {
25                parent[rootV] = rootU;
26                ++rank[rootU];
27            }
28        }
29    }
30    bool connected(int u, int v) {
31        return find(u) == find(v);
32    }
33};
34
35std::vector<bool> edgeLengthLimitedPaths(int n, std::vector<std::vector<int>>& edgeList, std::vector<std::vector<int>>& queries) {
36    UnionFind uf(n);
37    std::vector<bool> answers(queries.size(), false);
38    std::sort(edgeList.begin(), edgeList.end(), [](const std::vector<int>& a, const std::vector<int>& b) { return a[2] < b[2]; });
39    std::vector<std::pair<int, std::vector<int>>> sorted_queries;
40    for (int i = 0; i < queries.size(); ++i) {
41        sorted_queries.emplace_back(i, queries[i]);
42    }
43    std::sort(sorted_queries.begin(), sorted_queries.end(), [](const std::pair<int, std::vector<int>>& a, const std::pair<int, std::vector<int>>& b) { return a.second[2] < b.second[2]; });
44
45    int edgeIndex = 0;
46    for (const auto& [qIndex, qry] : sorted_queries) {
47        int p = qry[0], q = qry[1], limit = qry[2];
48        while (edgeIndex < edgeList.size() && edgeList[edgeIndex][2] < limit) {
49            uf.union_sets(edgeList[edgeIndex][0], edgeList[edgeIndex][1]);
50            ++edgeIndex;
51        }
52        answers[qIndex] = uf.connected(p, q);
53    }
54
55    return answers;
56}

1using System.Linq;

public class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int Find(int u) {
        if (u != parent[u]) {
            parent[u] = Find(parent[u]);
        }
        return parent[u];
    }

    public void Union(int u, int v) {
        int rootU = Find(u);
        int rootV = Find(v);
        if (rootU != rootV) {
            if (rank[rootU] > rank[rootV]) {
                parent[rootV] = rootU;
            } else if (rank[rootU] < rank[rootV]) {
                parent[rootU] = rootV;
            } else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
        }
    }

    public bool Connected(int u, int v) {
        return Find(u) == Find(v);
    }
}

public class Solution {
    public bool[] EdgeLengthLimitedPathsKruskal(int n, int[][] edgeList, int[][] queries) {
        var uf = new UnionFind(n);
        bool[] answers = new bool[queries.Length];
        Array.Sort(edgeList, (a, b) => a[2].CompareTo(b[2]));

        var indexedQueries = queries.Select((q, index) => new { q, index }).OrderBy(x => x.q[2]).ToArray();

        int edgeIndex = 0;
        foreach (var item in indexedQueries) {
            int p = item.q[0], q = item.q[1], limit = item.q[2], qIndex = item.index;
            while (edgeIndex < edgeList.Length && edgeList[edgeIndex][2] < limit) {
                uf.Union(edgeList[edgeIndex][0], edgeList[edgeIndex][1]);
                edgeIndex++;
            }
            answers[qIndex] = uf.Connected(p, q);
        }

        return answers;
    }
}