dfs树

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和最大。路径可以经过同一条边同一个点不过这样的路径的价值被计算相应次数。

显然一条路径出现两次相当于没出现。如何求这样的路径。可以考虑线性基求最大值。

巴特西

dfs树

$注：这是一个很显然也十分重要的性质。

最新文章

热门文章

巴特西

dfs树

$注：这是一个很显然 也十分重要的性质。

最新文章

热门文章

$注：这是一个很显然也十分重要的性质。