题目来源:https://www.luogu.com.cn/problem/P1525
答案导航:https://www.luogu.com.cn/record/230217157
没有学过拆点并查集,想了很久,用普通并查集+map(map用于维护互斥的点),但是有很多细节要抠,真的很复杂,A不出来啊!
呜呜呜无奈之下去找了ai老师解锁新区域了————拆点并查集(似乎也叫拓展域并查集?这个是二倍拓展,貌似可以几倍?
这道题是非常非常简单的一道几乎是拆点并查集的入门题,几乎一套就过没阻碍
那么就贴一下它和普通并查集比起来的核心增加处:
void uunion(int u, int v) { u = find(u); v = find(v); if (u == v) { return; } pp[u] = v; }
以及在主函数里的:
uunion(p[i].a + N, p[i].b); uunion(p[i].a, p[i].b + N);