并查集部分

程序员文章站 2022-03-16 08:13:12

功能①：合并两个集合void merge(int a, int b) {f[Find(a)] = Find(b);}②：查询某个元素的祖宗节点int Find(int x) {return x == f[x] ? x : f[x] = Find(f[x]);}扩展① 记录每个集合的大小(绑定到根节点)int pa = Find(a);int pb = Find(b);if(){ s[pb] += s[pa]}②每个点到根节点的距离(绑定到每一个元素身上)in...

功能

①：合并两个集合

void merge(int a, int b) {
	f[Find(a)] = Find(b);
}

②：查询某个元素的祖宗节点

int Find(int x) {
	return x == f[x] ? x : f[x] = Find(f[x]);
}

扩展

① 记录每个集合的大小(绑定到根节点)

int pa = Find(a);
int pb = Find(b);
if(){
    s[pb] += s[pa]
}

②每个点到根节点的距离(绑定到每一个元素身上)

int n, p[N], s[N], d[N];
//p[x] x的父亲节点  d[x] x到父节点的距离   s[x] 集合的大小
int Find(int x) { //距离查找
	if (p[x] != x) {
		int root = Find(p[x]);
		d[x] += d[p[x]];
		p[x] = root;
	}
	return p[x];
}

int pa = Find(a);
int pb = Find(b);
if () { //距离更新
	p[pa] = pb;
	d[pa] = s[pb];
	s[pb] += s[pa];
}

AcWing1250. 格子游戏

Alice和Bob玩了一个古老的游戏：首先画一个 n×n 的点阵（下图 n=3）。

接着，他们两个轮流在相邻的点之间画上红边和蓝边：

并查集部分

直到围成一个封闭的圈（面积不必为 1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了，他们的游戏实在是太长了！

他们甚至在游戏中都不知道谁赢得了游戏。

于是请你写一个程序，帮助他们计算他们是否结束了游戏？

输入格式

输入数据第一行为两个整数 n 和 m。n表示点阵的大小，m 表示一共画了 m 条线。

以后 m 行，每行首先有两个数字 (x,y)，代表了画线的起点坐标，接着用空格隔开一个字符，假如字符是 D，则是向下连一条边，如果是 R 就是向右连一条边。

输入数据不会有重复的边且保证正确。

输出格式

输出一行：在第几步的时候结束。

假如 m 步之后也没有结束，则输出一行“draw”。

数据范围

$1 \leq n \leq 200$
$1 \leq m \leq 24000$

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) { return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 50000;
int f[N];
int n,m;
int Find(int x) {
	return x == f[x] ? x : f[x] = Find(f[x]);
}

int get(int x, int y) {
	return x * n + y;
}

void merge(int a, int b) {
	f[Find(a)] = Find(b);
}

int main() {
	cin >> n >> m;

	for (int i = 0; i < N;++i)f[i] = i;
	int res = 0;
	for (int i = 1; i <= m;++i) {
		int x, y;
		char d;
		cin >> x >> y >> d;
		int a = get(x, y);
		int b = 0;
		if (d == 'D')b = get(x + 1, y);
		else b = get(x, y + 1);

		if (Find(a) != Find(b))merge(a, b);
		else {
			res = i;
			break;
		}
	}

	if (!res)puts("draw");
	else cout << res << endl;
	return 0;
}

AcWing1252. 搭配购买

思路

先分组再做01背包

Joe觉得云朵很美，决定去山上的商店买一些云朵。

商店里有 n 朵云，云朵被编号为 1,2,…,n，并且每朵云都有一个价值。

但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。

但是Joe的钱有限，所以他希望买的价值越多越好。

输入格式

第 1 行包含三个整数 n，m，w表示有 n 朵云，m 个搭配，Joe有 w 的钱。

第 2∼n+1行，每行两个整数 $c_{i}$ ， $d_{i}$ 表示 i 朵云的价钱和价值。

第 n+2∼n+1+m行，每行两个整数 $u_{i}$ ， $v_{i}$ 表示买 $u_{i}$ 就必须买 $v_{i}$ ，同理，如果买 $v_{i}$ 就必须买 $u_{i}$ 。

输出格式

一行，表示可以获得的最大价值。

数据范围

$1 \leq n \leq 10000$
$0 \leq m \leq 5000$
$1 \leq w \leq 10000$
$1 \leq c i \leq 5000$
$1 \leq d i \leq 100$
$1 \leq u i, v i \leq n$

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) { return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 10010;
int f[N], p[N], v[N], w[N];
int n, m, val;

int Find(int x) {
	return x == p[x] ? x : p[x] = Find(p[x]);
}


int main() {
	cin >> n >> m >> val;
	for (int i = 1;i <= n;++i)p[i] = i;
	for (int i = 1; i <= n;++i) {
		cin >> v[i] >> w[i];
	}

	while (m--) {
		int a, b;
		cin >> a >> b;
		int pa = Find(a);
		int pb = Find(b);

		if (pa != pb) {
			v[pb] += v[pa];
			w[pb] += w[pa];
			p[pa] = p[pb];
		}
	}
	for (int i = 1;i <= n;++i) {
		if (p[i] == i) {
			for (int j = val;j >= v[i];--j)
				f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	}
	cout << f[val] << endl;

	return 0;
}

AcWing237. 程序自动分析

思路

先把相等的合并再判断不相等是否与已知条件矛盾

在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本：假设 $x_{1},x_{2},x_{3}$ ,…代表程序中出现的变量，给定n个形如 $x_{i}=x_{j}$ 或 $x_{i}≠x_{j}$ 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。

例如，一个问题中的约束条件为： $x_{1}=x_{2}，x_{2}=x_{3}，x_{3}=x_{4}，x_{1}≠x_{4}$ ，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

现在给出一些约束满足问题，请分别对它们进行判定。

输入格式

输入文件的第1行包含1个正整数t，表示需要判定的问题个数，注意这些问题之间是相互独立的。

对于每个问题，包含若干行：

第1行包含1个正整数n，表示该问题中需要被满足的约束条件个数。

接下来n行，每行包括3个整数i,j,e，描述1个相等/不等的约束条件，相邻整数之间用单个空格隔开。若e=1，则该约束条件为 $x_{i}=x_{j}$ ；若e=0，则该约束条件为 $x_{i}≠x_{j}$ 。

输出格式

输出文件包括t行。

输出文件的第k行输出一个字符串“YES”或者“NO”（不包含引号，字母全部大写），“YES”表示输入中的第k个问题判定为可以被满足，“NO”表示不可被满足。

数据范围

$1 \leq n \leq 1000000$
$1 \leq i, j \leq 1000000000$

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#include<unordered_map>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) { return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 2000010;
int f[N], n, m;
unordered_map<int, int>S;


struct Query {
	int x, y, e;
}query[N];
int Find(int x) {
	return x == f[x] ? x : f[x] = Find(f[x]);
}

int get(int x) {
	if (S.count(x) == 0)S[x] = ++n;
	return S[x];
}
int main() {
	int t;cin >> t;
	while (t--) {
		S.clear();
		n = 0;
		
		scanf("%d", &m);
		for (int i = 0; i < m;++i) {
			int x, y, e;
			scanf("%d%d%d", &x, &y, &e);
			query[i] = { get(x),get(y),e };
		}
		
		for(int i = 1; i <= n;++i)f[i] = i;
		bool has = false;
		for (int i = 0; i < m;++i) {
			if (query[i].e == 1)f[Find(query[i].x)] = Find(query[i].y);
		}

		for (int i = 0;i < m;++i) {
			if (query[i].e == 0 && Find(query[i].x) == Find(query[i].y)) {
				has = true;
				break;
			}
		}

		if (has)puts("NO");
		else puts("YES");
	}

	return 0;
}

AcWing238. 银河英雄传说

有一个划分为N列的星际战场，各列依次编号为1,2,…,N。

有N艘战舰，也依次编号为1,2,…,N,其中第i号战舰处于第i列。

有T条指令，每条指令格式为以下两种之一：

1、M i j，表示让第i号战舰所在列的全部战舰保持原有顺序，接在第j号战舰所在列的尾部。

2、C i j，表示询问第i号战舰与第j号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。

现在需要你编写一个程序，处理一系列的指令。

输入格式

第一行包含整数T，表示共有T条指令。

接下来T行，每行一个指令，指令有两种形式：M i j或C i j。

其中M和C为大写字母表示指令类型，i和j为整数，表示指令涉及的战舰编号。

输出格式

你的程序应当依次对输入的每一条指令进行分析和处理：

如果是M i j形式，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；

如果是C i j形式，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目，如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。

数据范围

$N \leq 30000, T \leq 500000$

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#include<unordered_map>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) { return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 30030;
int n, p[N], s[N], d[N];

int Find(int x) {
	if (p[x] != x) {
		int root = Find(p[x]);
		d[x] += d[p[x]];
		p[x] = root;
	}
	return p[x];
}

int main() {
		for (int i = 1;i < N;++i) {
			p[i] = i;
			s[i] = 1;
		}
		
		int n;scanf("%d", &n);
		while (n--) {
			char op[2];int a, b;
			scanf("%s%d%d", op, &a, &b);
			int pa = Find(a);
			int pb = Find(b);
			if (op[0] == 'M') {
				p[pa] = pb;
				d[pa] = s[pb];
				s[pb] += s[pa];
			}

			else {
				if (pa == pb)printf("%d\n", max(0, abs(d[a] - d[b]) - 1));
				else printf("-1\n");
			}
		}

	return 0;
}

AcWing239. 奇偶游戏

思路

$s_{i} = a_{1} + a_{2} +\dots +a_{i}$ 前i个数中1的个数

$s [l - r]$ 中有奇数个1

$\iff$ $s_{r} - s_{l-1}$ 为奇数

$\iff$ $s_{r}$ 与 $s_{l-1}$ 奇偶性不同

偶数个1 $\iff$ $s_{r}$ 与 $s_{l - 1}$ 奇偶性相同

小A和小B在玩一个游戏。

首先，小A写了一个由0和1组成的序列S，长度为N。

然后，小B向小A提出了M个问题。

在每个问题中，小B指定两个数 l 和 r，小A回答 S[l~r] 中有奇数个1还是偶数个1。

机智的小B发现小A有可能在撒谎。

例如，小A曾经回答过 S[1~3] 中有奇数个1， S[4~6] 中有偶数个1，现在又回答 S[1~6] 中有偶数个1，显然这是自相矛盾的。

请你帮助小B检查这M个答案，并指出在至少多少个回答之后可以确定小A一定在撒谎。

即求出一个最小的k，使得01序列S满足第1 ~ k个回答，但不满足第1~k+1个回答。

输入格式

第一行包含一个整数N，表示01序列长度。

第二行包含一个整数M，表示问题数量。

接下来M行，每行包含一组问答：两个整数l和r，以及回答“even”或“odd”，用以描述S[l~r] 中有偶数个1还是奇数个1。

输出格式

输出一个整数k，表示01序列满足第1_{k个回答，但不满足第1}k+1个回答，如果01序列满足所有回答，则输出问题总数量。

数据范围

$N \leq 109, M \leq 10000$

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#include<unordered_map>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) { return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 20050;

unordered_map<int, int>s;
int n, m;
int p[N], d[N];

int get(int x) {
	if (s.count(x) == 0)s[x] = ++n;
	return s[x];
}

int Find(int x) {
	if (x != p[x]) {
		int root = Find(p[x]);
		d[x] ^= d[p[x]];
		p[x] = root;
	}
	return p[x];
}
int main() {
	cin >> n >> m;
	n = 0;
	for (int i = 1;i < N;++i)p[i] = i;
	int res = m;

	for (int i = 1;i <= m;++i) {
		int a, b;
		string op;
		cin >> a >> b >> op;
		a = get(a - 1), b = get(b);

		int t = 0; //偶数
		if (op == "odd")t = 1; //奇数
		int pa = Find(a), pb = Find(b);

		if (pa == pb) {
			if ((d[a] ^ d[b]) != t) {
				res = i - 1;
				break;
			}
		}
		else {
			p[pa] = pb;
			d[pa] = d[a] ^ d[b] ^ t;
		}
	}
	cout << res << endl;
}

本文地址：https://blog.csdn.net/zzq0523/article/details/109251782

相关标签：学习收藏 java 数据结构 python 算法大数据

上一篇：东芝存储XS700固态移动硬盘上手：速度给力

下一篇：微软公布大消息：Windows 10用户超过8亿

并查集部分

功能

扩展

AcWing1250. 格子游戏

输入格式

输出格式

数据范围

代码

AcWing1252. 搭配购买

思路

输入格式

输出格式

数据范围

代码

AcWing237. 程序自动分析

思路

输入格式

输出格式

数据范围

代码

AcWing238. 银河英雄传说

输入格式

输出格式

数据范围

代码

AcWing239. 奇偶游戏

思路

输入格式

输出格式

数据范围

代码

c# linq的差集,并集,交集,去重代码(分享)

Zend Framework教程之连接数据库并执行增删查的方法(附demo源码下载)

Python求两个list的差集、交集与并集的方法

java编程实现并查集的路径压缩代码详解

L2-007 家庭房产（并查集）

java8 集合求差集、并集、交集的实例

python 集合 并集、交集 Series list set 转换的实例

SQL语句的并集UNION 交集JOIN(内连接，外连接)等介绍

PHP自动识别字符集并完成转码详解

JS计算两个数组的交集、差集、并集、补集（多种实现方式）

python 集合并集、交集 Series list set 转换的实例