首页 > 代码库 > bzoj 2075: [POI2004]KAG
bzoj 2075: [POI2004]KAG
整天鬼畜题搞搞，感觉药丸……
这种题出到xjoi模拟题里，太神了……
这题的核心在于分割Cograph，尝试把Cograph的合成过程给求出来。
我们将这张图中的边为黑边，在这张图的补图中出现的边为白边，则黑边和白边构成了一个完全图。
1.如果当前这张图的黑边是不联通的，那么可以检查所有的黑边构成的联通块是不是Cograph，如果都是Cograph，则原图也为Cograph
2.如果当前这张图的白边是不联通的，那么可以检查所有的白边构成的联通块是不是Cograph，如果都是Cograph，则原图也为Cograph
3.如果当前这张图中的白边黑边都是联通的，直接返回该图不是Cograph
这样做显然是正确的，但是时间复杂度太高了，每次划分的复杂度是\(O(m)\)的，由于白边有\(O(n^2)\)条，因此这个做法也是\(O(n^2)\)
显然是会爆炸……
考虑优化这个做法，我们并不需要枚举所有白边，当找到一条白边时，就将它所连接的两个白联通块合并，合并次数是\(O(n)\)的
因此需要一种支持快速 合并联通块、查询一个联通块到另一个联通块之间所有边的数据结构……
这里用链表维护联通块……（为什么不用并查集？因为我要访问该联通块所有的点
这样就可以保证每次查询的边一定是不在当前同一个联通块中，
查询的两个点间要么是黑边要么是白边，黑边只有\(O(m)\)条，由于只有\(O(n)\)次合并，因此扫到的白边只有\(O(n)\)条，时间复杂度是\(O(n + m)\)的
这样对于一个问题，只需要\(O(n + m)\)就可以把它变成若干个小原问题了。
由于Cograph每层的分割至少有\(O(n)\)条连接在白联通块之间的黑边被删除了，因此这样分割的层数是\O(min(m / n, n)\)的
总时间复杂度\O((n + m)\sqrt(n)\)
跑的稍微有点慢啊~
#include <bits/stdc++.h>#define N 300000using namespace std; vector <int> bi[N], bn[N];int T, n, m;int ai[N];int nx[N], ne[N], nl[N], tot;int vis[N], td[N], tt[N], col[N];int tmp;void dfs1(int t, int c){ vis[t] = c; for (int i = 0; i < bi[t].size(); ++ i) if (!vis[bi[t][i]]) dfs1(bi[t][i], c);}int solve2(int t);int solve1(int t){ int nw = tmp + 1; for (int p = t; p; p = nx[p]) vis[p] = 0; for (int p = t; p; p = nx[p]) if (!vis[p]) dfs1(p, vis[p] = ++ tmp); for (int p = t; p; p = nx[p]) { if (!tt[vis[p]]) tt[vis[p]] = td[vis[p]] = p; else { nx[td[vis[p]]] = p; td[vis[p]] = p; } } for (int i = nw; i <= tmp; ++ i) { nx[td[i]] = 0; if (!solve2(tt[i])) return 0; } return 1;}set <int> S[N];int test(int a, int b){ return S[a].count(b);}int solve2(int t){ if (nx[t] == 0) return 1; for (int p = t; p; p = nx[p]) ne[p] = nx[p], nl[p] = p; for (int p = t; p; p = ne[p]) nx[p] = 0; for (int p = t; p; p = ne[p]) { for (int a = p; a; a = nx[a]) { for (int q = ne[p], c = p; q; ) { int bo = 0; for (int b = q; b; b = nx[b]) if (!test(a, b)) { bo = 1; goto haha; } haha: if (bo) { nx[nl[p]] = q; nl[p] = nl[q]; nl[q] = 0; ne[c] = ne[q]; ne[q] = 0; q = ne[c]; } else { c = ne[c]; q = ne[q]; } } } } if (ne[t] == 0) return 0; for (int p = t; p; p = ne[p]) for (int q = p; q; q = nx[q]) col[q] = p, bn[q].clear(); for (int p = t; p; p = ne[p]) for (int q = p; q; q = nx[q]) for (int a = 0; a < bi[q].size(); ++ a) if (col[bi[q][a]] == col[q]) bn[q].push_back(bi[q][a]); for (int p = t; p; p = ne[p]) for (int q = p; q; q = nx[q]) bi[q] = bn[q]; vector <int> nls; for (int p = t; p; p = ne[p]) nls.push_back(p); for (int p = 0; p < nls.size(); ++ p) if (!solve1(nls[p])) return 0; return 1;}int main(){ //freopen("C.in", "r", stdin); scanf("%d", &T); while (T --) { scanf("%d%d", &n, &m); for (int i = 1; i <= m; ++ i) { int a, b; scanf("%d%d", &a, &b); bi[a].push_back(b); S[a].insert(b); bi[b].push_back(a); S[b].insert(a); } for (int i = 1; i < n; ++ i) nx[i] = i + 1, ne[i] = 0; nx[n] = 0; if (solve1(1)) puts("TAK"); else puts("NIE"); for (int i = 1; i <= n; ++ i) bi[i].clear(), S[i].clear(); }}
bzoj 2075: [POI2004]KAG