30分求教
  • 板块P1551 亲戚
  • 楼主MZL193
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/6/12 19:49
  • 上次更新2024/6/12 20:13:58
查看原帖
30分求教
479946
MZL193楼主2024/6/12 19:49
#include<stdio.h>

const int maxn = 5010;

int father[maxn];

// fa[4] = 3, fa[3] = 1
// fa[1] = 1
void init(int n) {
	for(int i=0; i<=n; i++) {
		father[i] = i;
	}
}
int findFather(int x) {
	int fx = father[x];
	if(fx == x) {
		return fx;
	}
	return father[x] = findFather(fx);
}

bool isSame(int x, int y) {
	int fx = findFather(x), fy = findFather(y);
	return fx == fy;
}

void combile(int x, int y) {
	int fx = findFather(x), fy = findFather(y);
	if(fx < fy) {
		father[x] = father[y] = fx;
	} else {
		father[x] = father[y] = fy;
	}
}

int main()
{
	int n, m, p, x, y;
	scanf("%d%d%d", &n, &m, &p);
	init(n);
	for(int i=0; i<m; i++) {
		scanf("%d%d", &x, &y);
		combile(x, y);
	}
	for(int i=0; i<p; i++) {
		scanf("%d%d", &x, &y);
		if(isSame(x, y)) {
			printf("Yes\n");
		} else {
			printf("No\n");
		}
	}
	return 0;
}
2024/6/12 19:49
加载中...