【数据结构】并查集

Alex_Shen
2020-11-15 / 0 评论 / 0 点赞 / 87 阅读 / 2,904 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-04-06,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

问题 A: 并查集基础

题目描述

现在有一个并查集,你需要完成合并和查询操作。

输入

第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。
接下来M 行,每行包含三个整数 Zi,Xi,Yi 。
当 Zi=1 时,将 Xi 与 Yi 所在的集合合并。
当Zi=2 时,输出Xi 与 Yi 是否在同一集合内,是的输出 Y ;否则输出 N 。

输出

对于每一个Zi=2 的操作,都有一行输出,每行包含一个大写字母,为 Y 或者 N 。

样例输入

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

样例输出

N
Y
N
Y

题解

#include<iostream>
using namespace std;

struct node {
	int x, y, z;
};

node a[100];

int parent[100];

int getparent(int x) {
	if (parent[x] == x)
		return x;
	parent[x] = getparent(parent[x]);
	return parent[x];
}

void Union(int a, int b) {
	int fx, fy;
	fx = getparent(a);
	fy = getparent(b);
	parent[fx] = fy;
}

void Judge(int a,int b) {
	int px, py;
	px = getparent(a);
	py = getparent(b);
	if (px == py)
		cout << "Y" << endl;
	else
		cout << "N" << endl;
}

int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		cin >> a[i].z >> a[i].x >> a[i].y;
		parent[i] = i;
	}
	for (int i = 1; i <= M; i++) {		
		switch (a[i].z) {
		case 1:Union(a[i].x, a[i].y); break;
		case 2:Judge(a[i].x, a[i].y); break;
		}
	}
	return 0;
}

问题 B: 红娘

题目描述

小明在A公司工作,小红在B公司工作。A公司有N名男员工,其中有P对有朋友关系。B公司有M名女员工,其中有Q对有朋友关系。假设朋友的朋友还是朋友。
每对朋友关系用两个整数(Xi, Yi)组成,表示朋友的编号分别为Xi,Yi。男人的编号是正数,女人的编号是负数。小明的编号是1,小红的编号是-1.
小明和小红是情侣,他们想撮合A、B公司的员工成为情侣。只有异性男女才能成为情侣,而且任何一方都不能脚踏两只船哦。那么,请问两公司之间,通过小明和小红认识的人最多一共能配成多少对情侣。(包括他们自己)

输入

第1行,4个空格隔开的正整数N,M,P,Q。
之后P行,每行两个正整数, Xi, Yi。
之后Q行,每行两个负整数, Xi, Yi。

输出

一个正整数,表示通过小明和小红认识的人最多一共能配成多少对情侣。(包括他们自己)

样例输入

4 3 4 2
1 1
1 2
2 3
1 3
-1 -2
-3 -3

样例输出

2

题解

#include<iostream>
using namespace std;

int male[10000], female[10000];

int getparent(int a, int* x) {
	if (x[a] == a)
		return a;
	x[a] = getparent(x[a], x);
	return x[a];
}

void Union(int a, int b, int* x) {
	int fx, fy;
	fx = getparent(a, x);
	fy = getparent(b, x);
	if (fx > fy)
		swap(fx, fy);
	x[fy] = fx;
}

int Count(int* x, int a) {
	int count = 0;
	for (int i = 1; i <= a; i++) {
		if (getparent(x[i], x) == 1)
			count++;
	}
	return count;
}

int main() {
	int N, M, P, Q;
	cin >> N >> M >> P >> Q;

	for (int i = 1; i <= N; i++) {
		male[i] = i;
	}
	for (int i = 1; i <= M; i++) {
		female[i] = i;
	}
	for (int i = 1; i <= P; i++) {
		int a, b;
		cin >> a >> b;
		Union(a, b, male);
	}
	for (int i = 1; i <= Q; i++) {
		int a, b;
		cin >> a >> b;
		Union(-a, -b, female);
	}
	cout << min(Count(male, N), Count(female, M)) << endl;
	return 0;
}

问题 C: 滑雪

题目描述

David是个滑雪初学者,他还没有学会如何在滑行过程中控制方向,也不知道如何停下来。所以他的滑行方式只能是在一个高高的雪堆上调整好向北,东,南或西移动的方向,然后直线滑下来,一直滑倒另一个雪堆底下才能停下来。
他发觉以这种方式,有些雪堆他是无法到达的。因此,他现在想在已有的雪堆基础上,自己再人为地增加一些雪堆,使得他可以从任何雪堆转移到其他任何雪堆。他请求您帮他找到需要创建的雪堆的最少数量。
我们假设David只能在整数坐标处堆积雪堆。
在这里插入图片描述

输入

输入的第一行包含一个整数n(1≤n≤100),表示已有的雪堆数量。 接下来的n行中的每行包含两个整数Xi和Yi(1≤Xi,Yi≤1000),表示已有的第i个雪堆的坐标。
请注意,北方向与Oy轴方向一致,因此东方向与Ox轴方向一致。 所有雪堆的位置都不同。

输出

输出为使David能够从任何雪堆到达其他任何雪堆而需要创建的最小雪堆数。

样例输入

2
2 1
1 2

样例输出

1

题解

#include <iostream>
using namespace std;
int parent[101];
struct node
{
    int x, y;
};

int getparent(int x)
{
    if (parent[x] == x)
        return x;
    parent[x] = getparent(parent[x]);
    return parent[x];
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i <= n; ++i)
        parent[i] = i;
    int ans = 0;
    node* point = new node[n];
    for (int i = 0; i < n; ++i)
        cin >> point[i].x >> point[i].y;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j)
        {
            if (point[i].x == point[j].x || point[i].y == point[j].y)
            {
                int px = getparent(i);
                int py = getparent(j);
                if (px != py)
                {
                    ans++;
                    parent[py] = px;
                }
            }
        }
    }
    cout << n - 1 - ans << endl;
    return 0;
}

0

评论区