guest@cp-base:~/home$

Graph

(11)

Graph algorithms: shortest paths, SCC, LCA

$ls graph/|wc -l11 templates found
template_tarjan.cpp

Tarjan's Algorithm

[Graph]

SCC decomposition, bridges, and articulation points in a single O(V+E) DFS pass.

#tarjan#scc#bridges+2
$ cat tarjan
template_prim-mst.cpp

Prim's MST

[Graph]

Minimum spanning tree using priority queue — greedy cut-based approach in O(E log V).

#prim#mst#minimum-spanning-tree+1
$ cat prim-mst
template_lca-weighted.cpp

LCA Weighted

[Graph]

LCA with path aggregate queries (sum/max/min) on weighted trees using binary lifting in O(log n).

#lca#binary-lifting#weighted-tree+2
$ cat lca-weight..
template_lca.cpp

LCA — Lowest Common Ancestor

[Graph]

Binary lifting for LCA, distance, and k-th ancestor queries on unweighted trees in O(log n).

#lca#binary-lifting#tree+1
$ cat lca
template_kuhn-matching.cpp

Kuhn's Matching

[Graph]

Maximum bipartite matching via augmenting paths in O(V*E).

#bipartite#matching#kuhn+1
$ cat kuhn-match..
template_graph-traversal.cpp

Graph Traversal

[Graph]

DFS and BFS with bipartite check, cycle detection, topological sort, and path reconstruction.

#dfs#bfs#bipartite+2
$ cat graph-trav..
template_graph-representation.cpp

Graph Representation

[Graph]

Linked-list (head array) adjacency — cache-friendly graph representation for contests.

#graph#adjacency-list#head-array+1
$ cat graph-repr..
template_floyd-warshall.cpp

Floyd-Warshall

[Graph]

All-pairs shortest paths via O(V^3) dynamic programming on the adjacency matrix.

#floyd-warshall#all-pairs#shortest-path+2
$ cat floyd-wars..
template_dijkstra.cpp

Dijkstra's Algorithm

[Graph]

Shortest path in non-negative weighted graphs using priority queue relaxation in O((V+E) log V).

#dijkstra#shortest-path#priority-queue+1
$ cat dijkstra
template_centroid-decomposition.cpp

Centroid Decomposition

[Graph]

Divide-and-conquer on trees via centroid selection for O(n log n) path processing.

#centroid#decomposition#tree+1
$ cat centroid-d..
template_bellman-ford.cpp

Bellman-Ford

[Graph]

Shortest path with negative edge weights and negative cycle detection in O(V*E).

#bellman-ford#shortest-path#negative-weights+1
$ cat bellman-fo..