玄关求条。
查看原帖
玄关求条。
1062532
MinLand楼主2024/10/22 14:24
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

namespace awa {
	const int N = 14;
	int T, fa[N], d[N], s[N]; //father, distance, size

	int fnd(int x) {
		if (fa[x] == x)
			return x;
		else {
			int fn = fnd(fa[x]);
			d[x] += d[fa[x]];
			return fa[x] = fn;
		}
	}
	void unite(int r1, int r2) {
		d[r1] += s[r2];
		fa[r1] = r2;
		s[r2] = s[r1] + s[r2];
		s[r1] = 0;
	}

	void solve() {
		cin >> T;
		for (int t = 1; t <= T; t++) {
			char op;
			int i, j;
			cin >> op >> i >> j;
			int r1 = fnd(i), r2 = fnd(j);
			if (op == 'M') {
				unite(r1, r2);
			}
			if (op == 'C') {
				if (r1 != r2)
					cout << "-1\n";
				else
					cout << abs(d[r1] - d[r2]) - 1 << '\n';
			}
		}
	}
	void init() {
		for (int i = 1; i <= N; i++)
			fa[i] = i, s[i] = 1, d[i] = 0;
	}
}
int main() {
	awa::init();
	awa::solve();
	return 0;
}

我表示实在找不到错误在哪里。T^T

样例里会输出两个负一,第二个是因为距离差为0。

2024/10/22 14:24
加载中...