语言月赛202304 - 写大作业：字符串相似性判断/n/n## 题目描述/n/n扶苏为了写计算理论大作业已经 36 小时没有合眼了。/n/n为了能快点睡觉，扶苏找到了 n 份文献，第 i 份文献是一个字符串 s_i，她打算把这些文献组合起来。/n/n具体来说，一共有两种操作：/n/n- 1 x y：把文献 s_x 整体拼接到 s_y 的后面，然后删除 s_x。/n- 2 x y：查询 s_x 和 s_y 是否'相似'。/n/n我们保证在 1 x y 操作出现后，字符串 s_x '不会'出现在接下来的任何操作中。这就是说，操作 1 至多有 n-1 次。/n/n'相似'的定义是：对两个字符串 s_x 和 s_y，如果存在一种重新排列 s_x 的方法，使得重排后的 s_x 和 s_y 相等，则称 s_x 和 s_y '相似'。/n/n例如，假设 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 相似。/n/n注意，操作 2 不会对字符串做出实际修改。/n/n## 输入格式/n/n第一行是两个整数，分别表示文献的数量 n 和操作的数量 q。/n接下来 n 行，每行一个字符串，第 i 行的字符串表示 s_i。/n接下来 q 行，每行三个整数 op, x, y，其含义见『题目描述』。/n/n## 输出格式/n/n对个操作 2，输出一行一个字符串。如果 s_x 和 s_y 相似，则输出 'Yes'，否则输出 'No'。/n/n## 样例 #1/n/n### 样例输入 #1/n/n/n4 4/nab/ncd/nabcd/nabcc/n1 1 2/n2 2 3/n2 3 4/n2 2 4/n/n/n### 样例输出 #1/n/n/nYes/nNo/nNo/n/n/n## 提示/n/n### 数据规模与约定/n/n- 对 30% 的数据，保证 n = 2，q = 1。/n- 对 60% 的数据，保证 n ≤ 6，q ≤ 6，|s_i| ≤ 6。/n- 对 100% 的数据，保证 2 ≤ n ≤ 10^5，1 ≤ q ≤ 10^6，1 ≤ o ≤ 2，1 ≤ x, y ≤ n，且输入字符串的总长度不超过 10^6，输入字符串仅含小写英文字母，且不是空串。/n用C++内容：cpp/n#include <iostream>/n#include <vector>/n#include <string>/n#include <algorithm>/n/nusing namespace std;/n/nvector<int> parent;/nvector<string> texts;/n/nint find(int x) {/n if (parent[x] == x) {/n return x;/n }/n return parent[x] = find(parent[x]);/n}/n/nvoid merge(int x, int y) {/n int parentX = find(x);/n int parentY = find(y);/n if (parentX != parentY) {/n parent[parentX] = parentY;/n }/n}/n/nbool similar(int x, int y) {/n string textX = texts[find(x)];/n string textY = texts[find(y)];/n sort(textX.begin(), textX.end());/n sort(textY.begin(), textY.end());/n return textX == textY;/n}/n/nint main() {/n int n, q;/n cin >> n >> q;/n parent.resize(n + 1);/n texts.resize(n + 1);/n for (int i = 1; i <= n; i++) {/n cin >> texts[i];/n parent[i] = i;/n }/n for (int i = 0; i < q; i++) {/n int op, x, y;/n cin >> op >> x >> y;/n if (op == 1) {/n merge(x, y);/n } else {/n cout << (similar(x, y) ? /'Yes/' : /'No/') << endl;/n }/n }/n return 0;/n}/n/