整天鬼畜题搞搞，感觉药丸……
这种题出到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{m})\)
跑的稍微有点慢啊~
#include <bits/stdc++.h>
#define N 300000
using 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 = ; 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 + ;
for (int p = t; p; p = nx[p]) vis[p] = ;
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]] = ;
if (!solve2(tt[i])) return ;
}
return ;
}
set <int> S[N];
int test(int a, int b)
{
return S[a].count(b);
}
int solve2(int t)
{
if (nx[t] == ) return ;
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] = ; 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 = ;
for (int b = q; b; b = nx[b])
if (!test(a, b))
{
bo = ;
goto haha;
}
haha:
if (bo)
{
nx[nl[p]] = q;
nl[p] = nl[q];
nl[q] = ; ne[c] = ne[q];
ne[q] = ;
q = ne[c];
}
else
{
c = ne[c];
q = ne[q];
}
}
}
}
if (ne[t] == ) return ;
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 = ; 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 = ; p < nls.size(); ++ p)
if (!solve1(nls[p])) return ;
return ;
}
int main()
{
//freopen("C.in", "r", stdin);
scanf("%d", &T);
while (T --)
{
scanf("%d%d", &n, &m);
for (int i = ; 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 = ; i < n; ++ i) nx[i] = i + , ne[i] = ;
nx[n] = ;
if (solve1()) puts("TAK"); else puts("NIE"); for (int i = ; i <= n; ++ i) bi[i].clear(), S[i].clear();
}
}