Codechef MAY15

leaf posted @ 2015年5月10日 15:02 in 未分类 , 668 阅读

GRAPHCNT 与 Dominator Tree

给你N个点M条边的有向图,问你无序二元组(X,Y)的个数,满足存在1->X与1->Y的路径,且不存在除了1以外的公共点。N<=100000

首先,要求出每个点到1上最先删去哪个点才能使它不与1联通。DAG可以搞搞每个点pre父亲,搞出一颗LCA树,但是不是DAG呢?

经邓司机指导,原来tarjan早在N年前已经解决了这个问题---Dominator Tree。可以参考LYD的讲稿。复杂度是O(N*a)的。

首先令T为一颗以r为根的有向有根树,即可以从r出发到达所有的点。

首先我们从r出发搞出一颗搜索树

idom(u)为u到根的最近必经点

semi(u)为u到根的最近半必经点。???就是在u的祖先中dfn[u]最小的点,且可以通过非树边不经过u到根上的其他的点到达u的点(好绕?)

看看y是u点,那么x是他的semi,应为x可以先跳绿的边,在跳蓝的边,跳到y

注意如果一个点实在找不到semi了,他的直接树上父亲也可以作为他的semi

 

那肿么求呢?

首先我们看看,假设从u连入一些边,比如v->u,如果dfn[v]<dfn[u],那么他是前向边(即从祖先过来的边)或树上的边,直接与semi取min即可

若dfn[v]>dfn[u],那么是后向边或横叉边(??脑补一下),那么v的一些最先的semi可以来更新答案。但不是所有的都可以,必须那些dfn比u大的点的semi可以来更新。为什么要dfn大于dfn[u]?因为如果小于的话,势必会经过u的祖先,于定义不符了。

具体求法:

先将点按dfn序大到小做

一开始将点的semi设为inf

然后枚举连向他的点,按照上面过程做。如何询问fn比u大的点的semi最小值?因为窝们从大往小做,所以dfn比大的都连在一块儿,用并查集维护即可。做完后将他和父亲连在一起即可

 

idom:

必经点定理:

一个点u的idom为:

u到semi[u]除了semi[u]以外路径上semi的最小值的那个点的idom值

具体做的时候可以在算semi是把每一个点挂到semi上,然后算出每个点的idom值是等于那个idom值,再顺推一遍即可

 

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>
using namespace std;
 
#define PII pair<int,int>
#define VPII vector<pair<int,int> >
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(x) ((int)x.size())
#define rep(i,a,b) for (int i = a; i <= b; ++i)
#define dep(i,a,b) for (int i = a; i >= b; --i)
typedef long long ll;
ll power(ll x,ll y,ll mod){ll res=1;while (y){if (y&1) res=res*x%mod;x=x*x%mod;y>>=1;}return res;}
 
const int nn=100010;
 
int siz[nn],fa[nn],dfn[nn],id[nn],semi[nn],idom[nn],anc[nn],best[nn];
vector<int> suc[nn],pre[nn],dom[nn];
int n,m,ti;
void dfs(int x)
{
	dfn[x]=++ti;id[ti]=x;
	semi[ti]=ti;
	best[ti]=ti;
	anc[ti]=ti;
	rep(i,0,sz(suc[x])-1)
	{
		int y=suc[x][i];
		if (!dfn[y]) dfs(y),fa[dfn[y]]=dfn[x];
	}
}
int get(int x)
{
	if (x==anc[x]) return x;
	int y=get(anc[x]);
	if (semi[best[x]]>semi[best[anc[x]]])
		best[x]=best[anc[x]];
	anc[x]=y;
	return y; 	
}
void work()
{
	dep(y,ti,1)
	{
		int x=fa[y];
		rep(i,0,sz(pre[id[y]])-1)
		{
			int z=dfn[pre[id[y]][i]];
			if (!z) continue;
			get(z);
			semi[y]=min(semi[y],semi[best[z]]);
		}
		dom[semi[y]].pb(y);
		rep(i,0,sz(dom[x])-1)
		{
			int z=dom[x][i];
			get(z);
			if (semi[best[z]]<x) idom[z]=best[z];
			else idom[z]=x;
		}
		anc[y]=x;
	}
	rep(i,2,ti) if (semi[i]!=idom[i]) idom[i]=idom[idom[i]];
	idom[1]=0;
}
int main()
{
//	freopen("1.in", "r", stdin);
//	freopen("1.out", "w", stdout);
	scanf("%d%d",&n,&m);
	rep(i,1,m)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		suc[x].pb(y);
		pre[y].pb(x);
	}
	dfs(1);
	work();
	ll res=(ll)ti*(ti-1)/2;
	dep(i,ti,2)
	{
		int x=id[i];
		siz[x]++;
		int fx=id[idom[i]];
		siz[fx]+=siz[x];
		if (idom[i] == 1) res-=(ll)siz[x]*(siz[x]-1)/2;
	}
	cout << res << endl;
	return 0;
} 

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter