小解析
问题:
- d[N]的含义?
- 注意,如果结论为真,需要将结论写入到目前的状态中。
答案:
代码中注释查看。
note: 理清楚这两个点就好了
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int p[N], d[N]; // 理解d[N]的含义,表示当前节点到其父节点的距离。默认时0.由于初始化是p[i] = i;
int res;
int find(int x)
{
if (p[x] != x) {
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) p[i] = i;
while (k--)
{
int D, x, y;
scanf("%d%d%d", &D, &x, &y);
if (x > n || y > n) res++;
else
{
int px = find(x), py = find(y);
if (D == 1)
{
if (px == py && (d[x] - d[y]) % 3) res++;
else if (px != py) // 关于这一步骤做的操作是,if判断了是假,就不错处理。否则,为真。则将真的内容更新到当前节点。
{
p[px] = py;
d[px] = d[y] - d[x];
}
}
else {
if (px == py && (d[x] - d[y] - 1) % 3) res++;
else if (px != py)
{
p[px] = py;
d[px] = d[y] - d[x] + 1;
}
}
}
}
printf("%d", res);
return 0;
}
大佬,为什么要%3???,不是很懂欸