Codechef MAY15

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

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;
} 
Avatar_small
ICICI Credit Card On 说:
2022年8月06日 20:29

ICICI has become one of the largest banking services in India. This is essentially because of their financial options that they provide to customers. Among them ICICI credit card online payment option has become a prominent one with eligible customers. ICICI Credit Card Online Payment Making full use of different types of cards available and then being able to make through different payment gateway in quick time as well. If this is your first time making your ICICI bank credit card payment then you can go through this article below. You may discuss different methods available that can help you make your payment in no time.


登录 *


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