dfs树是解决图中带环的利器。
前天CF的F题就是dfs树，但是当时我没有认真思考 觉着找到一个环过于困难 当时没有想到 也没理解dfs树的意义。
对于一张无向图求出一个dfs树 这个树有两种边 树边和非树边。
其中非树边连接的u v 他们一定具有祖先关系。
$注：这是一个很显然 也十分重要的性质。
应用：CF1325F Ehab's Last Theorem
给出一张无向联通图 且不存在重边 自环。定义\(m=\lceil sqrt(n)\rceil\)
求出图中一个环S 满足S是一个简单环 且\(|S|\geq m\)
或者求出图中一个independent set W 满足 W=m
求环或者求独立集 我们考虑一张无向图 很难求出最大的独立集 但是只是让求出一个大小为m的独立集。
考虑如何求环 dfs树。但是求不了最大环 但是我们要的也不是最大。我们利用非树边判断环的大小。
由于没有重边 自环 所以一个点连出w条非树边 那么显然有大小为w+1的环。
如果所有点都没有构成大小>=m的环 那说明每个点都最多有 m-2条非树边。
这个时候考虑最大独立集 当前点我们加入到我们的集合中 然后其最多影响m-2个点。
把能影响的都给标记了 最后我们发现最多能选 \(\lceil \frac{n}{m-1}\rceil\)个点 可以证明这个东西>=m.证毕。
所以我们直接上dfs树即可。值得注意的是 最后构造独立集的时候 需要从叶子节点构造。
可以证明 这样对其他节点的影响如上面的分析一样。
const int MAXN=200010;
int n,m,len=1,w,top,flag,cc;
int vis[MAXN],s[MAXN],d[MAXN],mark[MAXN],q[MAXN];
int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1];
inline void add(int x,int y)
{
ver[++len]=y;nex[len]=lin[x];lin[x]=len;
ver[++len]=x;nex[len]=lin[y];lin[y]=len;
}
inline void dfs(int x,int las)
{
if(flag)return;
vis[x]=1;s[++top]=x;
go(x)
{
if((i^1)==las)continue;
if(flag)break;
if(!vis[tn])
{
d[tn]=d[x]+1;
dfs(tn,i);
}
else if(d[x]-d[tn]+1>=w)
{
put(2);
put(d[x]-d[tn]+1);
int ww=d[x]-d[tn]+1;
while(ww)
{
printf("%d ",s[top]);
--top;--ww;
}
flag=1;
}
}
--top;
if(!mark[x])
{
q[++cc]=x;
go(x)mark[tn]=1;
}
}
int main()
{
freopen("1.in","r",stdin);
get(n);get(m);
rep(1,m,i)add(read(),read());
w=(int)ceil(sqrt(n*1.0));
//put(w);
dfs(1,-1);
if(flag)return 0;
put(1);rep(1,w,i)printf("%d ",q[i]);
return 0;
}
当然dfs树还有应用 如上次我写了一道bzoj 的电压 那道题是真的比较妙 dfs树上差分。最后证明的是 其他环都是无效的 有dfs树上的环即可。
一道例题：LINK:2115 Wc2011 Xor
给出一张有向无环图 求出1~n的一条路径使得其xor和最大。路径可以经过同一条边同一个点 不过这样的路径的价值被计算相应次数。
显然一条路径出现两次相当于没出现。如何求这样的路径。可以考虑线性基求最大值。