link_cut_tree_example.cc File Reference

Illustrative examples for Link-Cut Trees. More...

#include <iostream>
#include <tpl_link_cut_tree.H>

Include dependency graph for link_cut_tree_example.cc:

Go to the source code of this file.

Functions
static void	example_connectivity ()
static void	example_rerooting ()
static void	example_lca ()
static void	example_path_aggregates ()
static void	example_lazy_updates ()
int	main ()

Detailed Description

Illustrative examples for Link-Cut Trees.

Demonstrates:

1. Dynamic connectivity (link, cut, connected)
2. Rerooting a tree (make_root, find_root)
3. Lowest common ancestor (lca)
4. Path aggregates (sum, min, max)
5. Lazy path updates (path_apply)

Definition in file link_cut_tree_example.cc.

Function Documentation

example_connectivity()

static void example_connectivity ( )

static

Definition at line 53 of file link_cut_tree_example.cc.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::connected(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::cut(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::link(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_vertex().

Referenced by main().

example_lazy_updates()

static void example_lazy_updates ( )

static

Definition at line 239 of file link_cut_tree_example.cc.

References Aleph::divide_and_conquer_partition_dp(), and LL.

Referenced by main().

example_lca()

static void example_lca ( )

static

Definition at line 128 of file link_cut_tree_example.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::get_val(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::lca(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::link(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_root(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_vertex().

Referenced by main().

example_path_aggregates()

static void example_path_aggregates ( )

static

Definition at line 166 of file link_cut_tree_example.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::link(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_vertex(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::path_query(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::set_val().

Referenced by main().

example_rerooting()

static void example_rerooting ( )

static

Definition at line 94 of file link_cut_tree_example.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::find_root(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::get_val(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::link(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_root(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_vertex(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::path_size().

Referenced by main().

main()

int main

(

)

Definition at line 281 of file link_cut_tree_example.cc.

References example_connectivity(), example_lazy_updates(), example_lca(), example_path_aggregates(), and example_rerooting().