Java Snippets

dijkstra.java

package templates;

import java.util.*;

class Dijkstra {
    static class Pair {
        int x;
        long y;

        Pair(int x, long y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return String.format("(%d, %d)", x, y);
        }
    }

    ArrayList<ArrayList<Pair>> adj;
    long[] d;
    int[] par;
    public static final long INF = (long) 1e18;

    public Dijkstra(int n) {
        adj = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            adj.add(new ArrayList<Pair>());
        }
        d = new long[n];
        par = new int[n];
    }

    public void addEdge(int u, int v, long w) {
        --u;
        --v;
        adj.get(u).add(new Pair(v, w));
        adj.get(v).add(new Pair(u, w));
    }

    public void reset() {
        Arrays.fill(d, INF);
        Arrays.fill(par, -1);
    }

    public long[] run(int source) {
        reset();
        --source;
        PriorityQueue<Pair> q = new PriorityQueue<Pair>((a, b) -> {
            if (b.y == a.y) {
                return b.x - a.x;
            }
            return b.y == a.y ? 0 : b.y < a.y ? 1 : -1;
        });
        d[source] = 0;
        q.add(new Pair(source, 0));
        while (!q.isEmpty()) {
            Pair c = q.poll();
            if (c.y != d[c.x])
                continue;
            for (Pair p : adj.get(c.x)) {
                int v = p.x;
                long w = p.y;
                if (d[c.x] + w < d[v]) {
                    d[v] = d[c.x] + w;
                    par[v] = c.x;
                    q.add(new Pair(v, d[v]));
                }
            }
        }
        return Arrays.copyOf(d, d.length);
    }

    public List<Integer> getPath(int s, int t) {
        ArrayList<Integer> path = new ArrayList<Integer>();
        --s;
        --t;
        int c = t;
        while (c != s) {
            path.add(c + 1);
            c = par[c];
        }
        path.add(s + 1);
        Collections.reverse(path);
        return path;
    }

}

DSU.java

package templates;

import java.util.*;

class DSU {
    int n;
    int[] par;

    public DSU(int n) {
        this.n = n;
        this.par = new int[n];
        reset();
    }

    public void reset() {
        for (int i = 0; i < n; ++i) {
            par[i] = i;
        }
    }

    private int find(int x) {
        if (x == par[x])
            return x;
        return par[x] = find(par[x]);
    }

    public void union(int x, int y) {
        x = find(x);
        y = find(y);
        par[x] = y;
    }

    public boolean same(int x, int y) {
        return find(x) == find(y);
    }

    public int uniq() {
        HashSet<Integer> S = new HashSet<Integer>();
        for (int i = 0; i < n; ++i) {
            S.add(find(i));
        }
        return S.size();
    }
}

Mod.java

package templates;

final class Mod {
    public static long M = (long) 1e9 + 7;;
    public static long[] F, invF;
    private static boolean generated = false;

    public static long add(long a, long b) {
        return (a % M + b % M) % M;
    }

    public static long sub(long a, long b) {
        long res = (a % M - b % M) % M;
        if (res < 0)
            res += M;
        return res;
    }

    public static long mul(long a, long b) {
        return (a % M) * (b % M) % M;
    }

    public static long div(long a, long b) {
        return mul(a, inv(b));
    }

    public static long inv(long a) {
        return pow(a, 2L);
    }

    public static long pow(long a, long b) {
        long res = 1;
        while (b > 0) {
            if (b % 2L == 1L) {
                res = mul(res, a);
            }
            b /= 2L;
            a = mul(a, a);
        }
        return res;
    }

    public static void genFact(int n) {
        if (generated)
            return;
        int N = (int) 1.1e6;
        F = new long[N];
        invF = new long[N];
        F[0] = F[1] = invF[0] = invF[1] = 1L;
        for (int i = 2; i <= n; ++i) {
            F[i] = mul(i, F[i - 1]);
        }
        invF[n] = inv(F[n]);
        for (int i = n - 1; i >= 2; --i) {
            invF[i] = mul(i + 1, invF[i + 1]);
        }
        generated = true;
    }

    public static long fact(int n) {
        if (!generated) {
            throw new Error("call genFact() first");
        }
        if (n > F.length) {
            throw new Error("n too big for fact()");
        }
        return F[n];
    }

    public static long invFact(int n) {
        if (!generated) {
            throw new Error("call genFact() first");
        }
        if (n > F.length) {
            throw new Error("n too big for invFact()");
        }
        return invF[n];
    }

    public static long C(int n, int r) {
        if (!generated) {
            throw new Error("call genFact() first");
        }
        if (r <= 0 || n < r)
            return 0;
        return mul(F[n], mul(invF[r], invF[n - r]));
    }

}

template.java

import java.util.*;
import java.io.*;

public class Main {
	static InputStream inputStream;
	static OutputStream outputStream;
	static InputReader in;
	static PrintWriter out;
	static int MULTIPLE_TESTCASES = 1;
	static String PROB_NAME = "";

	///////////////////////////////////////
	// solution
	///////////////////////////////////////
	static class Solution {

		public void solve(int tc) throws IOException {

		}
	}

	private static void precompute() {

	}

	///////////////////////////////////////
	// template
	///////////////////////////////////////
	public static void main(String[] args) throws IOException {
		inputStream = System.in;
		outputStream = System.out;
		if (PROB_NAME != "") {
			inputStream = new FileInputStream(new File(PROB_NAME + ".in"));
			outputStream = new FileOutputStream(new File(PROB_NAME + ".out"));
		}
		in = new InputReader(inputStream);
		out = new PrintWriter(outputStream);
		int tc = 1;
		if (MULTIPLE_TESTCASES > 0)
			tc = in.ni();
		precompute();
		Solution sol = new Solution();
		for (int i = 1; i <= tc; ++i) {
			sol.solve(i);
		}
		in.close();
		out.close();
	}

	static class InputReader {
		BufferedReader reader;
		StringTokenizer st;

		public InputReader(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			st = null;
		}

		public String ns() throws IOException {
			while (st == null || !st.hasMoreTokens()) {
				st = new StringTokenizer(reader.readLine());
			}
			return st.nextToken();
		}

		public Long nl() throws IOException {
			return Long.parseLong(ns());
		}

		public Integer ni() throws IOException {
			return Integer.parseInt(ns());
		}

		public int[] nia(int n) throws IOException {
			int[] a = new int[n];
			for (int i = 0; i < n; ++i) {
				a[i] = ni();
			}
			return a;
		}

		public long[] nla(int n) throws IOException {
			long[] a = new long[n];
			for (int i = 0; i < n; ++i) {
				a[i] = nl();
			}
			return a;
		}

		public void close() throws IOException {
			reader.close();
		}
	}
}