[CodeChef FEB14]Graph Challenge解题报告(求半支配点)

题意

给一张有向图,使得从1开始按某种顺序DFS,可以让每个点的标号等于其DFS序号。求每个点的半支配点。

题解

使用Lengauer Tarjan算法,对这一算法的描述和证明见我的上一篇博文:

当然本题只需要求半支配点。
首先按照适当顺序DFS,还原题目描述中所称的DFS生成树。然后直接套算法。
代码如下,思路很简单。要点都写在注释中了。

#include
#include
#include
#include
#include
using namespace std;
const int SIZEN=100010;
void getint(int &x){
	char c=0;
	for(;c<'0'||c>'9';c=getchar());
	for(x=0;'0'<=c&&c<='9';c=getchar()) x=x*10+c-'0';
}
int N,M,Q;
vector c[SIZEN],ct[SIZEN];
int timer=0,fa[SIZEN];
int ufs[SIZEN],best[SIZEN],sdom[SIZEN];
int find(int x){//将x连接到路径最上端,并计算出一路上诸点的best 
	if(x==ufs[x]) return x;
	int y=find(ufs[x]);
	if(sdom[best[ufs[x]]]=1;i--){
		for(int j=0;ji的那些,find之后得到了它到根的最优sdom
			注意,对于第二种情况,u~v这一路上必然全大于i*/
			int u=ct[i][j];
			find(u);
			sdom[i]=min(sdom[i],sdom[best[u]]);
		}
		ufs[i]=fa[i];
	}
}
bool vis[SIZEN];
void DFS(int x){
	vis[x]=true;
	timer++;
	for(int i=0;i

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注