Euler Tour Technique

C++

1const int MX = 2e5+5;
2vector<int> adj[MX];
3int timer = 0, st[MX], en[MX];
4
5void dfs(int node, int parent) {
6    st[node] = timer++;
7    for (int i : adj[node]) {
8        if (i != parent) {
9            dfs(i, node);
10        }

Java

1public static void dfs(int i, int p) {
2    st[i] = timer++;
3    for (int next : g[i]) {
4        if(next != p) dfs(next, i);
5    }
6    en[i] = timer-1;
7}

C++

1/**
2 * Description: 1D point update, range query where \texttt{comb} is
3    * any associative operation. If $N=2^p$ then \texttt{seg[1]==query(0,N-1)}.
4 * Time: O(\log N)
5 * Source: 
6    * http://codeforces.com/blog/entry/18051
7    * KACTL
8 * Verification: SPOJ Fenwick
9 */
10

Java

1import java.util.*;
2import java.io.*;
3
4public class Main {
5    public static int[] st;
6    public static int[] en;
7    public static int timer, n;
8    public static ArrayList<Integer> g[];
9   
10    //Segtree code

C++

1int n; // The number of nodes in the graph
2vector<int> graph[100000];
3int timer = 0, tin[100000], euler_tour[200000];
4int segtree[800000]; // Segment tree for RMQ
5
6void dfs(int node = 0, int parent = -1) {
7    tin[node] = timer; // The time when we first visit a node
8    euler_tour[timer++] = node;
9    for (int i : graph[node]) {
10        if (i != parent) {

Java

1import java.util.*;
2import java.io.*;
3
4public class LCA {
5    public static int[] euler_tour, tin;
6    public static int timer, size, N;
7    public static ArrayList<Integer> g[];
8   
9    //Segtree code
10    public static final int maxsize = (int)1e7;  // limit for array size

C++