最近の公的祖先であるLCA問題
最近の共通祖先問題:ルートツリーを与え、2つのノードの最近の共通祖先を求める.ノードの祖先は、ノードからルートへのパス上のノードの集合です.
素朴なアルゴリズム:uの父から木に沿ってuの祖先を列挙し、リストLに保存し、vの祖先を列挙し、vの祖先がuの祖先に初めて現れたことを発見したとき、出力する.
オンラインLCAアルゴリズム:L(u)をuの深さとし、L(u)LCAのオフライン(Tarjan)アルゴリズム:DFS+を利用してセットを調べ、アルゴリズムフロー:新しく検索されたノードに対して、まずこのノードからなる集合を作成し、現在のノードの各サブツリーを検索し、1本のサブツリーを検索するたびに、サブツリー内のLCAクエリが解決したことを決定することができる.他のLCAクエリの結果は必然的にこのサブツリーの外にあり,このときサブツリーによって形成された集合を現在のノードの集合と統合し,現在のノードをこの集合の祖先とする.その後、現在のノードのすべてのサブツリーが検索されるまで、次のツリーを検索し続けます.このとき現在のノードもチェック済みとするとともに、現在のノードに関するLCAクエリを処理することができ、現在のノードからノードvへのクエリがあり、vがチェックされている場合、深さ優先探索が行われているため、現在のノードとvの最近の共通の祖先はまだチェックされていないに違いないが、この最近の共通の祖先を含むvのサブツリーはすでに検索されているに違いない.では、この最近の公共の祖先はvが集まっている祖先に違いない.アルゴリズムの疑似コードは次のとおりです.
POJ 1330タイトルリンク:http://poj.org/problem?id=1330現在の問題は,隣接テーブルを用いて格納できる要素uを含む集合を確立することである.隣接テーブルとは何か、データ構造については、ベクトルを隣接テーブルとして使用することをお勧めします.
ベクトルの方法:
隣接テーブルの用途は比較的に多く、隣接テーブルに関する知識を書くと、隣接テーブルは図のチェーンストレージ構造であり、図中の各頂点に対して単一チェーンテーブルを構築し、i番目の単一チェーンテーブルのノードは頂点viに依存するエッジ(対有向図は頂点viを尾とする弧)を表す.
次に、隣接テーブルを使用します.
隣接表テンプレート、転載:http://blog.acmol.com/
しかし、隣接するテーブルテンプレートにはいくつかの小さな変種があります.一、一部の図ではエッジの重み値を保存する必要がありません.この場合、Len配列を省くことができ、add関数ではlenというパラメータは必要ありません.二、ある点から出発する辺の数を使うことがある.1つのSize配列で記録し、add時にSize配列の値を増やせばよい.
三、最大ストリームでは、順方向エッジを追加するたびに容量が0の逆方向エッジを追加する必要がある.
四、最小費用最大ストリームにおいて、一般的に容量が0であり、費用が順方向エッジ費用の反対数であるエッジを追加する必要がある.
LCA問題に関するテーマ:POJ 14701986632373728,.3417,HDU 2586126928743380など~
素朴なアルゴリズム:uの父から木に沿ってuの祖先を列挙し、リストLに保存し、vの祖先を列挙し、vの祖先がuの祖先に初めて現れたことを発見したとき、出力する.
オンラインLCAアルゴリズム:L(u)をuの深さとし、L(u)
void LCA(u)
{ MAKE-SET(u);// , u, u
ancestor[Find-SET(u)]=u;
for(u v)
{ LCA(v);
Union(u,v);
ancestor[Find-SET(u)]=u;
}
color[u]=black;
for(Q(u) v) // (u,v)
{ if(color[v]==black)
{ ancestor[Find-SET(v)](u,v );
}
}
}
POJ 1330タイトルリンク:http://poj.org/problem?id=1330現在の問題は,隣接テーブルを用いて格納できる要素uを含む集合を確立することである.隣接テーブルとは何か、データ構造については、ベクトルを隣接テーブルとして使用することをお勧めします.
ベクトルの方法:
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
const int MAX=10010;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
int n,father[MAX],rank[MAX],ancestors[MAX],Indegree[MAX];
vector<int> Adj[MAX],temp[MAX];
bool visited[MAX];
void Init()
{ for(int i=0;i<MAX;i++)
{ father[i]=i;
Adj[i].clear();
temp[i].clear();
}
fill(rank,rank+MAX,1);
CLR(visited,false);
}
int Find(int u)
{ return father[u]==u?u:Find(father[u]);
}
void Union(int u,int v)
{ u=Find(u);
v=Find(v);
if(u==v) return ;
if(rank[u]>rank[v])
{ rank[u]+=rank[v];
father[v]=u;
}
else
{ rank[v]+=rank[u];
father[u]=v;
}
}
void LCA(int u)
{ ancestors[Find(u)]=u;//
for(vector<int>::size_type i=0;i<Adj[u].size();i++)
{ LCA(Adj[u][i]);//DFS~~~
Union(u,Adj[u][i]);
ancestors[Find(u)]=u;
}
visited[u]=true;
for(vector<int>::size_type i=0;i<temp[u].size();i++)
{ if(visited[temp[u][i]])
cout<<ancestors[Find(temp[u][i])]<<endl;
}
}
int main()
{ int k,u,v;
scanf("%d",&k);
while(k--)
{ scanf("%d",&n);
Init();
for(int i=0;i<n-1;i++)
{ scanf("%d%d",&u,&v);
Adj[u].push_back(v);
Indegree[v]++;
}
scanf("%d%d",&u,&v);
temp[u].push_back(v);
temp[v].push_back(u);
for(int i=1;i<=n;i++)
if(!Indegree[i])
{ LCA(i);//
break;
}
}
return 0;
}
隣接テーブルの用途は比較的に多く、隣接テーブルに関する知識を書くと、隣接テーブルは図のチェーンストレージ構造であり、図中の各頂点に対して単一チェーンテーブルを構築し、i番目の単一チェーンテーブルのノードは頂点viに依存するエッジ(対有向図は頂点viを尾とする弧)を表す.
次に、隣接テーブルを使用します.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX=10010;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
int n,Indegree[MAX],ancestors[MAX];
bool visited[MAX];
class UnionFindSet {
public:
void Union(int u,int v)
{ u=Find(u),v=Find(v);
if(u==v) return ;
if(rank[u]>rank[v])
{ rank[u]+=rank[v];
father[v]=u;
}
else
{ rank[v]+=rank[u];
father[u]=v;
}
}
int Find(int u)
{ return father[u]==-1?u:Find(father[u]);
}
void Init()
{ CLR(father,-1);
fill(rank,rank+MAX,1);
}
private:
int father[MAX];
int rank[MAX];
}U;
struct ArcNode{
void Link(int u,int v)
{ next[num]=prior[u];
data[num]=v;
prior[u]=num++;
}
void Init()
{ CLR(prior,-1);num=0;}
int prior[MAX],next[MAX],data[MAX],num; //prior[] , ,next[] ,data[]
}Arc,Que;
void LCA(int u)
{ ancestors[U.Find(u)]=u;
for(int i=Arc.prior[u];i!=-1;i=Arc.next[i])
{ LCA(Arc.data[i]);
U.Union(u,Arc.data[i]);
ancestors[U.Find(u)]=u;
}
visited[u]=true;
for(int i=Que.prior[u];i!=-1;i=Que.next[i])
{ if(visited[Que.data[i]])
cout<<ancestors[U.Find(Que.data[i])]<<endl;
}
}
int main()
{ int u,v,n,k;
scanf("%d",&k);
while(k--)
{ U.Init();
Arc.Init(); Que.Init();
CLR(Indegree,0);
CLR(visited,false);
scanf("%d",&n);
for(int i=0;i<n-1;i++)
{ scanf("%d%d",&u,&v);
Arc.Link(u,v);
Indegree[v]++;
}
scanf("%d%d",&u,&v);
Que.Link(u,v); Que.Link(v,u);
for(int i=1;i<=n;i++)
if(!Indegree[i]) {LCA(i); break; }
}
return 0;
}隣接表テンプレート、転載:http://blog.acmol.com/
template<int Max,int MaxE>
struct Graph {
void add(int u,int v,int len)
{ Next[top]=Head[u];
Len[top]=len; //
Num[top]=v;
Head[u]=top++;
}
void init()
{ CLR(Head,-1);top=0;
}
int Head[Max],Next[MaxE],Num[MaxE],top,Len[MaxE];
}; しかし、隣接するテーブルテンプレートにはいくつかの小さな変種があります.一、一部の図ではエッジの重み値を保存する必要がありません.この場合、Len配列を省くことができ、add関数ではlenというパラメータは必要ありません.二、ある点から出発する辺の数を使うことがある.1つのSize配列で記録し、add時にSize配列の値を増やせばよい.
template<int Max,int MaxE>
struct Graph2 {
void add(int u,int v)
{ Next[top]=Head[u];
Num[top]=v;
Head[u]=top++;
Size[u]++;
}
void init()
{ CLR(Head,-1);CLR(Size,0);top=0;
}
int Head[Max],Next[MaxE],Num[MaxE],Size[Max],top;
}; 三、最大ストリームでは、順方向エッジを追加するたびに容量が0の逆方向エッジを追加する必要がある.
四、最小費用最大ストリームにおいて、一般的に容量が0であり、費用が順方向エッジ費用の反対数であるエッジを追加する必要がある.
LCA問題に関するテーマ:POJ 14701986632373728,.3417,HDU 2586126928743380など~