语言月赛202304 - 写大作业：相似文献判定

题目描述

扶苏为了写计算理论大作业已经 36 小时没有合眼了。

为了能快点睡觉，扶苏找到了 n 份文献，第 i 份文献是一个字符串 s_i，她打算把这些文献组合起来。

具体来说，一共有两种操作：

'1 x y'：把文献 s_x 整体拼接到 s_y 的后面，然后删除 s_x。
'2 x y'：查询 s_x 和 s_y 是否'相似'。

我们保证在 '1 x y' 操作出现后，字符串 s_x '不会'出现在接下来的任何操作中。这就是说，操作 1 至多有 n-1 次。

'相似'的定义是：对两个字符串 s_x 和 s_y，如果存在一种重新排列 s_x 的方法，使得重排后的 s_x 和 s_y 相等，则称 s_x 和 s_y '相似'。

例如，假设 s_1 = 'ab', s_2 = 'cd', s_3 = 'abcd'，则执行 '1 1 2' 后，s_1 被删除，s_2 = 'cdab', s_3 = 'abcd'；继续执行 '2 2 3' 后，因为可以把 s_2 重排为 'abcd'，所以 s_2 和 s_3 相似。

注意，操作 2 不会对字符串做出实际修改。

输入格式

第一行是两个整数，分别表示文献的数量 n 和操作的数量 q。
接下来 n 行，每行一个字符串，第 i 行的字符串表示 s_i。
接下来 q 行，每行三个整数 op, x, y，其含义见『题目描述』。

输出格式

对个操作 2，输出一行一个字符串。如果 s_x 和 s_y 相似，则输出 'Yes'，否则输出 'No'。

样例 #1

样例输入 #1

4 4
ab
cd
abcd
abcc
1 1 2
2 2 3
2 3 4
2 2 4

样例输出 #1

Yes
No
No

提示

数据规模与约定

对 30% 的数据，保证 n = 2，q = 1。
对 60% 的数据，保证 n ≤ 6，q ≤ 6，|s_i| ≤ 6。
对 100% 的数据，保证 2 ≤ n ≤ 10^5，1 ≤ q ≤ 10^6，1 ≤ o ≤ 2，1 ≤ x, y ≤ n，且输入字符串的总长度不超过 10^6，输入字符串仅含小写英文字母，且不是空串。用C++内容：```cpp #include #include #include #include <unordered_map>

using namespace std;

// 并查集 class UnionFind { private: vector parent; vector rank;

public: UnionFind(int n) { parent.resize(n); rank.resize(n, 0); for (int i = 0; i < n; i++) { parent[i] = i; } }

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

void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) {
        return;
    }
    if (rank[rootX] < rank[rootY]) {
        parent[rootX] = rootY;
    } else if (rank[rootX] > rank[rootY]) {
        parent[rootY] = rootX;
    } else {
        parent[rootY] = rootX;
        rank[rootX]++;
    }
}

};

int main() { int n, q; cin >> n >> q;

vector<string> documents(n);
for (int i = 0; i < n; i++) {
    cin >> documents[i];
}

UnionFind uf(n);

// 记录文献中每个字符的数量
vector<unordered_map<char, int>> count(n);
for (int i = 0; i < n; i++) {
    for (char c : documents[i]) {
        count[i][c]++;
    }
}

for (int i = 0; i < q; i++) {
    int op, x, y;
    cin >> op >> x >> y;
    x--;
    y--;

    if (op == 1) {
        // 将文献x拼接到文献y后面，并删除文献x

        // 更新文献y的字符数量
        for (auto [c, cnt] : count[x]) {
            count[y][c] += cnt;
        }

        // 合并文献x和文献y的集合
        uf.unite(x, y);
    } else if (op == 2) {
        // 查询文献x和文献y是否相似

        // 如果文献x和文献y不属于同一集合，则肯定不相似
        if (uf.find(x) != uf.find(y)) {
            cout << "No" << endl;
            continue;
        }

        // 检查文献x和文献y的字符数量是否一致
        if (count[x] != count[y]) {
            cout << "No" << endl;
            continue;
        }

        cout << "Yes" << endl;
    }
}

return 0;

}