社区讨论

P1551 亲戚 样例过 0分求调

学术版参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@m4f303rc
此快照首次捕获于
2024/12/08 12:06
去年
此快照最后确认于
2025/11/04 13:09
4 个月前
查看原帖
https://www.luogu.com.cn/problem/P1551 代码
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n, ans;
ll bin[50005], c[50005];
int zx(int x) {
	int z;
	if (bin[x] == x) {
	//	cout << "fanhui" << x << "\n";
		return x;
	} else {
	//	cout << "digui\n";
		z = zx(bin[x]);
//		bin[x] = z;  //路径压缩
	}
	//cout << "fanhui" << z << "\n";
	return z;
}
int main() {
	int n, m, p;
	cin >> n >> m >> p;
	for (int i = 1; i <= n; i++) {
		bin[i] = i;
	}
	int a, b;
	while (m--) {
		cin >> a >> b;
		bin[b] = a;
	}
	for (int i = 1; i <= p; i++) {
		cin >> a >> b;
		if (zx(a) == zx(b)) {
			c[i] = 1;
		}
	}
	for (int i = 1; i <= p; i++) {
		if (c[i] == 1) {
			cout << "\nYes";
		} else {
			cout << "\nNo";
		}
	}
	return 0;
}
//	ios::sync_with_stdio(false);
思路:先把每个人(bin)的祖先设为自己,然后把两个人的祖先进行比较,如果一样,就是亲戚,c数组是暂时存储是不是亲戚的,祖先zx函数是查找祖先的

回复

4 条回复,欢迎继续交流。

正在加载回复...