1832.判断句子是否为全字母句

链接：1832.判断句子是否为全字母句
难度：Easy
标签：哈希表、字符串
简介：请你返回一个 布尔数组  answer ，其中  answer.length == queries.length ，当  queries[j]  的查询结果为  true  时， answer 第  j  个值为  true ，否则为  false 。

题解 1 - cpp

• 编辑时间：2022-12-14
• 执行用时：480ms
• 内存消耗：108.3MB
• 编程语言：cpp
• 解法介绍：先按照 limit 对 queries 排序，再进行离线查询，对于满足 limit 的边进行并查集联合，最后判断是否是同一个并查集中。

#include <vector>
// bestlyg
#define X first
#define Y second
#define lb(x) ((x) & (-x))
#define mem(a,b) memset(a,b,sizeof(a))
#define debug freopen("input","r",stdin)
#define PII pair<int,int>
#ifdef DEBUG
#define log(frm, args...) {    printf(frm, ##args);}
#else
#define log(frm, args...)
#endif
typedef long long ll;
using namespace std;
class UnionFind {
public:
    int n;
    vector<int> data, cnt;
    UnionFind(int n): n(n), data(vector<int>(n, 0)), cnt(vector<int>(n, 1)) {
        iota(data.begin(), data.end(), 0);
    }
    int size(int v) { return cnt[find(v)]; }
    int find(int v) {
        if (data[v] == v) return v;
        return data[v] = find(data[v]);
    }
    void uni(int v1, int v2) {
        int p1 = find(v1), p2 = find(v2);
        if (p1 != p2) {
            cnt[p1] += cnt[p2];
            data[p2] = p1;
        }
    }
    bool same(int v1, int v2) { return find(v1) == find(v2); }
};
int pos2Idx(int x, int y, int size) { return x * size + y; }
void idx2Pos(int idx, int size, int &x, int &y) { x = idx / size; y = idx % size; }
vector<vector<int>> dirs = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
// START
class Solution {
public:
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
        vector<int> qlist(queries.size());
        vector<bool> ans(queries.size(), false);
        iota(qlist.begin(), qlist.end(), 0);
        sort(qlist.begin(), qlist.end(), [&](auto &i1, auto &i2){ return queries[i1][2] < queries[i2][2]; });
        sort(edgeList.begin(), edgeList.end(), [&](auto &a, auto &b){ return a[2] < b[2]; });
        UnionFind uf(n);
        int j = 0;
        for (auto &i : qlist) {
            auto &q = queries[i];
            for (; j < edgeList.size() && edgeList[j][2] < q[2]; j++) uf.uni(edgeList[j][0], edgeList[j][1]);
            ans[i] = uf.same(q[0], q[1]);
        }
        return ans;
    }
};
// END
#ifdef LOCAL
int main() {
    return 0;
}
#endif