本文主要是介绍缝合的作品（并查集/逆序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
、思路：首先是并查集来做，首先给给每个单词一个id，然后把它放到ans[i]处。
对于操作1：把a单词换为单词b，就相当于a、b两个集合结合。然后再给a单词赋一个新的id，用来进行操作2，因为之后的操作2可能会出现a这个单词，并且没有转化为b单词，就需要一个新的id。
对于操作2：就是改变一下答案中目标位置的单词即可。
-----------------------------------
逆序的话，就是倒着从最晚操作的来改变文章
操作1：就是简单的把单词a改为单词b。
操作2：因为当前操作排在后面，当前面无论做什么改变当前位置单词也不会改变。
代码：
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define endl '\n'
#define pq priority_queue
using namespace std;
typedef pair<int,int> pii;
const int N = 100010;int n, q;
vector<string>ans(N);
map<string,int>mp;
int p[N];int find(int x){if(x != p[x])p[x] = find(p[x]);return p[x];
}void solve(){cin >> n >> q;vector<int>novel(n);int num = 0;auto getid = [&] (const string &s, bool override = false){if(!mp.count(s) || override){ans[num] = s;mp[s] = num ++;}return mp[s];};for(int i = 1;i <= n + q * 2;i ++)p[i] = i;for(int i = 0;i < n;i ++){string s;cin >> s;novel[i] = getid(s);}while(q --){int op;cin >> op;if(op == 1){string x, y;cin >> x >> y;if(x == y || !mp.count(x))continue;p[find(getid(x))] = find(getid(y));getid(x, true);}else{string y;int k;cin >> k;cin >> y;novel[k - 1] = getid(y);}}for(int i = 0;i < n;i ++){cout << ans[find(novel[i])] << ' ';}
}void task(int TestCase) {int n, q;cin >> n >> q;vector<string> s(n);map<string, string> mp;for (auto &x : s) {cin >> x;mp[x] = x;}vector<array<string, 3>> opt;for (int i = 0; i < q; i++) {string x, y, z;cin >> x >> y >> z;opt.push_back({x, y, z});mp[z] = z;}vector<int> vis(n);for (int i = q - 1; i >= 0; i--) {auto &[x, y, z] = opt[i];if (x == "1") {mp[y] = mp[z];} else {int pos = stoi(y) - 1;if (!vis[pos]) {s[pos] = mp[z];vis[pos] = 1;}}}for (int i = 0; i < n; i++) {cout << (vis[i] ? s[i] : mp[s[i]]) << " \n"[i + 1 == n];}
}
signed main()
{
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);// int t = 1;// while(t--)// {// solve();// }task(1);return 0;
}
这篇关于缝合的作品（并查集/逆序）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
