语言月赛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，输入字符串仅含小写英文字母，且不是空串。

解题思路

我们可以使用并查集来解决这个问题。

首先，我们需要给每个文献分配一个唯一的标识符，我们可以使用数组id来保存每个文献的标识符。初始时，我们假设每个文献的标识符都是其自身的索引，即id[i] = i。

对于操作1 x y，我们将id[x]的根节点的父节点指向id[y]的根节点，即id[find(id[x])] = find(id[y])。这样，文献x就被拼接到了文献y的后面。

对于操作2 x y，我们只需要判断文献x和文献y的根节点是否相同，如果相同，则说明它们是相似的。

最后，我们需要定义一个函数find来查找节点x的根节点。如果id[x]不等于x，则递归地查找id[x]的根节点，并将id[x]的父节点指向根节点。

算法步骤

创建一个数组id，初始化为0。
对于每个操作：
- 如果操作是1 x y，则执行id[find(x)] = find(y)。
- 如果操作是2 x y，则判断find(x) == find(y)，如果相等则输出Yes，否则输出No。
定义函数find，如果id[x]不等于x，则递归调用find(id[x])并将id[x]的父节点指向根节点。最后返回根节点。

复杂度分析

时间复杂度：每个操作都需要查找根节点，所以总的时间复杂度为O(n + q)，其中n是文献的数量，q是操作的数量。
空间复杂度：需要一个数组id来保存文献的标识符，所以空间复杂度为O(n)。

#include <iostream>
#include <vector>
using namespace std;

vector<int> id;

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

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

    id.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        id[i] = i;
    }

    while (q--) {
        int op, x, y;
        cin >> op >> x >> y;

        if (op == 1) {
            id[find(x)] = find(y);
        } else if (op == 2) {
            if (find(x) == find(y)) {
                cout << 'Yes' << endl;
            } else {
                cout << 'No' << endl;
            }
        }
    }

    return 0;
}