[CodeChef FEB14]Graph Challenge解题报告（求半支配点）

题意

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

http://cogs.pro/cogs/problem/problem.php?pid=2117

题解

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

http://blog.csdn.net/wmdcstdio/article/details/49868575

当然本题只需要求半支配点。

首先按照适当顺序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

题意

题解

发表回复 取消回复

发表回复取消回复