Replace the Numbers （并查集 | 倒叙模拟）_随笔

Replace the Numbers （并查集 | 倒叙模拟） E. Replace the Numbers

[link](Problem - E - Codeforces)

题意

给你一个空的序列，有两种 *** 作 1 x : 从序列最后加入 x 1 x:从序列最后加入x 1 x:从序列最后加入x， 2 x y : 将当前序列里所有的 x 变成 y 2 x y: 将当前序列里所有的x变成y 2 x y:将当前序列里所有的x变成y。给你 q q q个 *** 作，输出 *** 作后的序列。

思路并查集维护

如果每次从头到尾遍历修改复杂度太高。因为是对于一个相同数的 *** 作，也就是对于集合的 *** 作，我们可以用并查集来维护（选取集合代表元素），记录每个位置是什么数，每个数在哪个位置，即可。

对于一个新加的数，如果前面出现过就直接将其合并到前面，否则就初始化这个数在的位置。

对于要修改的 x x x变 y y y，如果 y y y出现过直接将 x x x的代表元素合并到 y y y上，将 x x x置为不存在，如果 y y y没出现过那就将 y y y置为 x x x的位置，将 x x x位置的数改为 y y y，置 x x x不存在即可。

Code

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include  
#include 
#include 
#include  
#include 
#define x first
#define y second
#define debug(x) cout<<#x<<":"< PII;
typedef pair PDD;
typedef unsigned long long ULL;
const int N = 5e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
#define tpyeinput int
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
	e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N];
int f[N], vis[N], num[N];
int find(int x) {
	return x == f[x] ? x : f[x] = find(f[x]);
}
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int T; cin >> T;
	for (int i = 1; i <= T; i ++) {
		int op; cin >> op;
		if (op == 1) {
			int x; cin >> x;
			a[++n] = i, f[i] = i, vis[i] = x;
			if (num[x]) 				f[i] = num[x];			
			else num[x] = i;
		}
		else {
			int x, y; cin >> x >> y;
			if (x != y && num[x]) {
				if (num[y]) {
				f[num[x]] = num[y];
				num[x] = 0;
			}
			else {
				num[y] = num[x];
				vis[num[x]] = y;
				num[x] = 0;
			}
			}
		}
	}
	for (int i = 1; i <= n; i ++) cout << vis[find(a[i])] << ' ';
	cout << endl;
	return 0;
}

倒叙性质模拟

因为每个数可能会变多次，所以我们倒着来模拟， f [ y ] : y 变成什么 f[y]:y变成什么 f[y]:y变成什么，对于插入 *** 作如果 f [ x ] ! = 0 f[x]!=0 f[x]!=0我们直接插入 f [ x ] f[x] f[x]即可，对于改变 *** 作，如果 f [ y ] = = 0 f[y]==0 f[y]==0代表后面 y y y不会改变， f [ x ] = y f[x]=y f[x]=y即可，如果 f [ y ] ! = 0 f[y]!=0 f[y]!=0代表后面 f [ y ] f[y] f[y]变了 f [ x ] = f [ y ] f[x]=f[y] f[x]=f[y]即可（当前 *** 作被后面影响了），也有点路径压缩的感觉，最后正序输出即可。

Code

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include  
#include 
#include 
#include  
#include 
#define x first
#define y second
#define debug(x) cout<<#x<<":"< PII;
typedef pair PDD;
typedef unsigned long long ULL;
const int N = 5e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
#define tpyeinput int
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
	e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N][3];
vector ve;
int f[N];
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i][0];
		if (a[i][0] == 1) cin >> a[i][1];
		else cin >> a[i][1] >> a[i][2];
	}

	for (int i = n; i; i --) {
		if (a[i][0] == 1) {
			if (!f[a[i][1]]) ve.push_back(a[i][1]);
			else ve.push_back(f[a[i][1]]);
		}
		else {
			if (!f[a[i][2]]) f[a[i][1]] = a[i][2];
			else 		     f[a[i][1]] = f[a[i][2]];
		}
	} 
	
	reverse(ve.begin(), ve.end());
	for (auto x : ve) cout << x << ' ';
	cout << endl;
	return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址:https://54852.com/zaji/5713555.html

Replace the Numbers （并查集 | 倒叙模拟）

发表评论

评论列表（0条）