lca 解决最近公共祖先问题
怎么解决的呢, 这是个暴力dfs 记忆化,并且用利用 并查集维护;
1.dfs 是一个暴力枚举的过程,失败就返回上一层从上个状态继续枚举,没有用过的状态;
poj1470
题意
5 //五个点 从1-5 ,接下来有5行
5:(3) 1 4 2 //5节点连三个点
1:(0)
4:(0)
2:(1) 3
3:(0)
6 //六个询问
(1 5) //1 5 最近公共祖先;
(1 4)
(4 2)
(2 3)
(1 3)
(4 3)
输出
每个点 作为最近公共祖先 次数不为0的次数;
【lca问题总结_第一版】看lca 核心函数
int fin(int x)
{
int i=x;
while(f[i]!=i)
{
i=f[i];
}
return i;
}
void solve(int u)
{
int i,j;
vis[u]=1;
f[u]=u;
for(i=0;
i完整代码
#include
#include
#include
using namespace std;
const int N=1111;
int n,m,k;
int head[N*2],f[N*2],vis[N*2],x[N*N],y[N*N],
in[N*2],
cnt[N*2];
struct node
{
int v,w,next;
} edge[N*2];
void add(int u,int v,int w)
{
node E= {v,w,head[u]};
edge[k]=E;
head[u]=k++;
}
void init()
{
int i,j;
k=0;
for(i=0;
i> n )
{
init();
for(i = 0 ;
i < n;
i++)
{
//5:(3)
int u,v,cn;
scanf("%d:(%d)",&u,&cn);
// in[u]++;
for(j = 0;
j < cn;
j++)
{
scanf("%d",&v);
in[v]++;
add(u ,v ,0 );
add(v ,u ,0 );
}}
scanf("%d",&m);
for(i=0;
i
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
