http://acm.hdu.edu.cn/contests/contest_show.php?cid=886
1004 - Discovery of Cycles
题意:给定一张无向图,边集中的每条边给了编号,多次询问,问只保留编号在 [l,r] 的边,是否有环。
只要判断环,可以考虑并查集。但是这里有多次询问,说明需要动态修改加边删边,所以要考虑 LCT。
由于询问的端点可能抖动,所以即使离线后按照一维排序,另一维仍可能抖动,不能保证复杂度。
但是可以发现在一张已经有环的图上再加边并不会使得它没环,所以只要预处理出 i 作为左端点,第一次出现环时的右端点,再对于每个以 i 为左端点的询问,判断询问的右端点是否在预处理得到的右端点更右即可。
动态删边加边要用到 LCT,这里只需要一些基础操作,link 加边,cut 删边,findroot 用来找根判断是否已在同一棵树。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120
| #include<bits/stdc++.h> using namespace std; #define ll long long const int INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const int N = 5e6 + 10; const ll mod = 1e9 + 7; struct LCT { #define lc c[x][0] #define rc c[x][1] int f[N], c[N][2], siz[N]; bool r[N]; inline void init(int n) { for (int i = 0; i <= n; i++) { f[i] = c[i][0] = c[i][1] = r[i] = 0; siz[i] = 1; } } inline bool nroot(int x) { return c[f[x]][0] == x || c[f[x]][1] == x; } inline void rev(int x) { swap(lc, rc); r[x] ^= 1; } inline void pushdown(int x) { if (r[x]) { if (lc)rev(lc); if (rc)rev(rc); r[x] = 0; } } inline void update(int x) { siz[x] = siz[lc] + siz[rc]; } inline void rotate(int x) { int y = f[x], z = f[y], k = c[y][1] == x, w = c[x][k ^ 1]; if (nroot(y))c[z][c[z][1] == y] = x; if (w)f[w] = y; c[x][k ^ 1] = y; c[y][k] = w; f[y] = x; f[x] = z; update(y), update(x); } inline void pushall(int x) { if (nroot(x))pushall(f[x]); pushdown(x); } inline void splay(int x) { pushall(x); int y, z; while (nroot(x)) { y = f[x]; z = f[y]; if (nroot(y))rotate((c[y][0] == x && c[z][0] == y ? y : x)); rotate(x); } } inline void access(int x) { for (int y = 0; x; y = x, x = f[x]) splay(x), rc = y; } inline void makeroot(int x) { access(x); splay(x); rev(x); } int findroot(int x) { access(x); splay(x); while (lc)pushdown(x), x = lc; splay(x); return x; } inline void split(int x, int y) { makeroot(x); access(y); splay(y); } inline void link(int x, int y) { makeroot(x); if (findroot(y) != x)f[x] = y; } inline void cut(int x, int y) { makeroot(x); if (findroot(y) == x && f[y] == x && !c[y][0]) { f[y] = c[x][1] = 0; } } }lct; int T; int n, m, q; int u[N], v[N]; int a[N]; int main() { scanf("%d", &T); while (T--) { scanf("%d%d%d", &n, &m, &q); for (int i = 1; i <= m; i++) { scanf("%d%d", &u[i], &v[i]); } lct.init(n); fill(a, a + m + 1, INF); for (int l = 1, r = 1; l <= m; l++) { while (r <= m) { if (lct.findroot(u[r]) == lct.findroot(v[r])) { a[l] = r; break; } lct.link(u[r], v[r]); r++; } lct.cut(u[l], v[l]); } int ans = 0; while (q--) { int l, r; scanf("%d%d", &l, &r); l = (l^ans) % m + 1; r = (r^ans) % m + 1; if (l > r)swap(l, r); ans = (r >= a[l]); puts(ans ? "Yes" : "No"); } } return 0; }
|