锐客网

  1. 首页 > it技术 > >

hdu|【hdu 5354】Bipartite Graph【分治 并查集】

分治HDU并查集

给一张无向图，问删掉点i后改图是否为二分图。
Solve(l, r)表示要求l到r的答案。在并查集中先加上l~mid的边，Solve(mid + 1, r)，回溯。同理递归到Solve(l, mid)。
并查集要按秩合并。
也可用线段树（动态维护图连通性）。

#include #include #include #include #include #define Rep(i, x, y) for (int i = x; i <= y; i ++) #define Dwn(i, x, y) for (int i = x; i >= y; i --) #define RepE(i, x) for(int i = pos[x]; i; i = g[i].nex) using namespace std; typedef long long LL; const int N = 100005; struct Edge { int y, nex, z1, z2, z; } g[N * 2]; int T, n, m, pos[N], sz, par[N], sum[N], l, ans[N], p1[N]; void Init(int x, int y) { g[++ sz].y = y, g[sz].nex = pos[x], pos[x] = sz; } int Find(int x) { return (par[x] == x) ? x : (l = l ^ p1[x], Find(par[x])); } bool Check(int l1, int r1, int l2, int r2) { bool fl = 0; Rep(x, l1, r1) { RepE(i, x) { int y = g[i].y; if (y > r2 || y < l2) { int lx, ly, x0, y0; l = 0, x0 = Find(x), lx = l; l = 0, y0 = Find(y), ly = l; if (x0 != y0) { if (sum[x0] > sum[y0]) swap(x0, y0); par[x0] = y0; g[i].z1 = x0, g[i].z2 = y0, g[i].z = sum[y0]; p1[x0] = ((lx + ly) % 2 == 0); sum[y0] += sum[x0]; } else { g[i].z1 = -1; if ((lx + ly) % 2 == 0) fl = 1; } } else g[i].z1 = -1; } } return fl; } void Solve(int l, int r) { if (l == r) { ans[l] = 1; return ; } int mid = l + r >> 1; bool fl = Check(l, mid, mid + 1, r); if (fl) Rep(i, mid + 1, r) ans[i] = 0; else Solve(mid + 1, r); Rep(x, l, mid) { RepE(i, x) { int x0 = g[i].z1, y0 = g[i].z2; // cout << x0<<" "<



【hdu|【hdu 5354】Bipartite Graph【分治 并查集】】

    推荐阅读


    上一篇：数学|【Topcoder SRM 641】BitToggler 期望 高斯消元

    下一篇：数据结构|【NOI集训】【XJ】可持久化左偏树