文章

25

粉丝

0

获赞

0

访问

68446

头像
并查集+离散化
经验总结
发布于2020年4月19日 00:59
阅读数 2945

程序自动分析:

(1)并查集(路径压缩)+离散化(数据过大):

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 2e6 + 10;
vector<pair<int, int>>a, b;//a存放相等的约束条件,b存放不相等的约束条件
int father[N], id[N];//father用于并查集,id用于离散化映射
int x, y, c;//每一组约束条件输入
int t, n, m;//t表示测试用例个数,n表示约束条件的个数,m表示离散化id数组的元素个数
/* findfather(int x){//时间复杂度过大
	while (x != father[x]){
		x = father[x];
	}
	return father[x];
}*/
int findfather(int x) {//采用路径压缩
	return x == father[x] ? x : (father[x] = findfather(father[x]));
}
int getId(int x){
	return lower_bound(id + 1, id + 1 + m, x) - id;
}

void solve(){
	for (int i = 1; i <= m; i++){
		father[i] = i;
	}
	for (int i = 0; i < a.size(); i++){//相等约束条件将相等的元素放在同一个集合
		int x = getId(a[i].first); int y = getId(a[i].second);//获得数组下标
		int x_father = findfather(x); int y_father = findfather(y);
		father[x_father] = y_father;
	}
	for (int i = 0; i < b.size(); i++){
		int x = getId(b[i].first); int y = getId(b[i].second);
		int x_father = findfather(x); int y_father = findfather(y);
		if (x_father == y_father){
			printf("NO\n");
			return;
		}
	}
	printf("YES\n");
}

int main(){
	scanf("%d", &t);
	while (t--){
		a.clear(); b.clear();
		m = 0;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++){
			scanf("%d%d%d", &x, &y, &c);
			if (c == 1){//相等约束条件
				a.push_back({ x, y });
			}
			else{
				b.push_back({ x, y });
			}
			id[++m] = x; id[++m] = y;
		}
		sort(id + 1, id + 1 + m);
		m = unique(id + 1, id + 1 + m) - id - 1;//更新压缩冗余元素的个数
		solve();
	}
	
	return 0;
}

(2)并查集+map

#include<iostream>
#include<unordered_map>
using namespace std; 
const int N = 2e6 + 10;
int a[N][3], t, n, m, cnt, father[N], opt[N];//a[N][3]存放约束元素,opt[N]存放约束类型
unordered_map<int, int>c;
int findfather(int x) {//采用路径压缩
	return x == father[x] ? x : (father[x] = findfather(father[x]));
}
void union_set(int x, int y){
	father[findfather(x)] = findfather(y);
}

int main(){
	scanf("%d", &t);
	while (t--){
		scanf("%d", &n);
		n *= 3;//表示输入的数字个数
		for (int i = 1; i <= n; i++){
			int x;
			scanf("%d", &x);
			if (i % 3){//此时输入的x表示x的下标,不是约束类型
				if (c[x] == 0){//第一次输入x,则赋予一个数字进行映射
					c[x] = ++cnt;
					a[i / 3 + 1][i % 3] = c[x];//将赋予的数存起来
					father[c[x]] = c[x];//初始化并查集father[i]=i
				}
			}
			else{
				opt[i / 3] = x;//第x/3个约束条件的约束类型
			}
		}
		//离线操作
		int flag = false;
		for (int i = 1; i <= n / 3; i++){
			if (opt[i]){
				union_set(a[i][1], a[i][2]);
			}
		}
		for (int i = 1; i <= n / 3; i++){
			if (!opt[i]){
				if (findfather(a[i][1]) == findfather(a[i][2])){
					flag = true;
					printf("NO\n");
					break;
				}
			}
		}
		if (!flag){
			printf("YES\n");
		}

	}

	return 0;
}

 



登录后发布评论

暂无评论,来抢沙发