「OI之路」04图论-09其他

包括:环计数、树哈希判断同构、求补图的联通块信息

无向图k元环与k长简单路径计数

对于k=3,例题如jsoi2017原力,将点按照度数排序

1
2
3
4
5
6
7
for(auto x:pt)//bb为向后的边
{
for(auto y:bb[x]) vis[y]=1;
for(auto y:bb[x]) for(auto z:bb[y])
if(vis[z]) g3[x]++,g3[y]++,g3[z]++;
for(auto y:bb[x]) vis[y]=0;
}

分析复杂度,前面两层循环为$O(m)$,最后一个等于每个点出发向后的边数,对于度数小于m根号的点显然成立,对于度数大的点后面最多有根号m个点(因为这样的点最多根号个且都在后面),故总复杂度为$O(m^{3/2})$

对于k=4,例题如tkppc2016H デバッグ(Debug);大致思路就是在三元环的基础上处理些信息

对于每个四元环,枚举x表示度数最大节点,枚举中间点y和端点z并记录在z处

那么一个环其实就是$x-y-z和x-y’-z$组成的,将后者记录在cc里面从而唯一统计四元环,做完x的时候回退

某些题需要记录每个点作为四元环中一点的次数,那回退的时候顺便更新在以后作为$y’$的次数即可

通过向左可以让每个点作为y的次数为根号,而里面那层枚举to是从y开始找的,总复杂度为$O(m^{3/2})$

1
2
3
4
5
6
7
for(auto x:pt)//to为所有边,pos为排序后位置,cc就是对于当前x而言
{
for(auto y:to[x]) if(pos[y]<pos[x]) for(auto z:to[y])
if(pos[z]<pos[x]) g4[x]+=cc[z],g4[y]+=cc[z],g4[z]+=cc[z],cc[z]++;
for(auto y:to[x]) if(pos[y]<pos[x]) for(auto z:to[y])
if(pos[z]<pos[x]) cc[z]--,g4[y]+=cc[z];
}

关于k=4简单路径计数,也见tkppc2016 H デバッグ(Debug)

树哈希判断同构

主要是loj2072「JSOI2016」独特的树叶code,可能应该写双hash的偷懒没写

考虑我们设计出的hash方式需要满足一些怎样的性质

因为是无根树,我们需要计算出A树以每个节点为根的hash值,塞到一个map里面,然后对于B树考虑每个叶子节点x,去掉后这棵树以fa(x)为根的hash值,然后放到map里面查询

可见:应该满足与遍历孩子顺序无关,而且方便我们换根来求出每个点为根的值

满足这个条件基本可以$O(nlogn)$了,首先hash表之类的可能可以线性,具体怎么搞自行设计吧

目前抄的是:$f(x)=(\sum f(son)*siz_{son} \%mod) xor (siz_x*base \%mod)$

求补图的连通块信息

例题:CF1242B 0-1 MST,给出一种复杂度为$O(n+m)$的做法,正确性和复杂度都很显然就不解释了,只是不是特别好想而已

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
unordered_set<int> to[N],lef;
void gao(int rt)
{
queue<int> q;q.push(rt);lef.erase(rt);
while(sz(q))
{
int x=q.front();q.pop();
for(unordered_set<int>::iterator it=lef.begin();it!=lef.end();)
if(!to[x].count(*it)) q.push(*it),lef.erase(it++); else it++;
}
}
void main()
{
int n=qread(),m=qread();fo(i,1,n) lef.insert(i);
while(m--){int x=qread(),y=qread();to[x].insert(y),to[y].insert(x);}
int ans=-1;fo(i,1,n) if(lef.count(i)) gao(i),ans++;write(ans);
}//此代码写的是求连通块数

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/d107.html
转载请注明出处,谢谢!