Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/de/dde/lowest__common__ancestor_8cpp_source.html below:

TheAlgorithms/C++: graph/lowest_common_ancestor.cpp Source File

(

N,

std::vector<std::pair<int, int> > &undirected_edges) {

(

&edge : undirected_edges) {

[edge.first].push_back(edge.second);

[edge.second].push_back(edge.first);

(

std::vector<std::pair<int, int> > &undirected_edges,

: Graph(undirected_edges.size() + 1, undirected_edges),

(root_) {

std::queue<int> queue_of_vertices;

queue_of_vertices.push(

);

(!queue_of_vertices.empty()) {

vertex = queue_of_vertices.front();

queue_of_vertices.pop();

(

neighbor :

[vertex]) {

(

[neighbor] == -1) {

[neighbor] = vertex;

queue_of_vertices.push(neighbor);

(tree.level[v] > tree.level[u]) {

level_diff = tree.level[u] - tree.level[v];

(

i = 0; (1 << i) <= level_diff; ++i) {

(level_diff & (1 << i)) {

assert(tree.level[u] == tree.level[v]);

(

i =

(

[u].size()) - 1; i >= 0; --i) {

(

[u][i] !=

[v][i]) {

assert(

[u][0] ==

[v][0]);

std::vector<std::vector<int> >

;

.resize(tree.number_of_vertices());

(

vertex = 0; vertex < tree.number_of_vertices(); ++vertex) {

[vertex].push_back(tree.parent[vertex]);

(

level = 0; (1 << level) < tree.number_of_vertices(); ++level) {

(

vertex = 0; vertex < tree.number_of_vertices(); ++vertex) {

[vertex].push_back(

[

[vertex][level]][level]);

std::vector<std::pair<int, int> > edges = {

{7, 1}, {1, 5}, {1, 3}, {3, 6}, {6, 2}, {2, 9}, {6, 8}, {4, 3}, {0, 4}};

std::vector< std::vector< int > > neighbors

for each vertex it stores a list indicies of its neighbors

Graph(size_t N, const std::vector< std::pair< int, int > > &undirected_edges)

Populate the adjacency list for each vertex in the graph. Assumes that evey edge is a pair of valid v...

int number_of_vertices() const

std::vector< std::vector< int > > up

for every vertex stores a list of its ancestors by powers of two For each vertex, the first element o...

int lowest_common_ancestor(int u, int v) const

Query the structure to find the lowest common ancestor. Assumes that the provided numbers are valid i...

LowestCommonAncestor(const RootedTree &tree_)

Stores the tree and precomputs "up lifts".

std::vector< int > level

Stores the distance from the root.

std::vector< int > parent

Stores parent of every vertex and for root its own index. The root is technically not its own parent,...

RootedTree(const std::vector< std::pair< int, int > > &undirected_edges, int root_)

Constructs the tree by calculating parent for every vertex. Assumes a valid description of a tree is ...

int root

Index of the root vertex.

void populate_parents()

Calculate the parents for all the vertices in the tree. Implements the breadth first search algorithm...

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4