1. private static int gcd(int a, int b) {
    2.     return (b == 0) ? a : gcd(b, a % b);
    3. }
    1. private static int qpow(int a, int b, int p) {
    2.     int res = (int) 1;
    3.     while (b > 0) {
    4.         if ((b & 1) == 1) {
    5.             res = res * a % p;
    6.         }
    7.         a = a * a % p;
    8.         b >>= 1;
    9.     }
    10.     return res;
    11. }
    1. private static int find(int x) {
    2.     return (int) ((x == f[x]) ? x : (f[x] = find(f[x])));
    3. }
    5. private static void merge(int x, int y) {
    6.     int f1 = find(x);
    7.     int f2 = find(y);
    8.     f[f1] = f2;
    9. }
    1. for (int i = 1; i <= n; i ++ ) {
    2.     for (int j = 1; j <= n; j ++ ) {
    3.         if (i == j) {
    4.             g[i][j] = 0;
    5.         } else {
    6.             g[i][j] = INF;
    7.         }
    8.     }
    9. }
    11. private static void floyd() {
    12.     for (int k = 1; k <= n; k ++ ) {
    13.         for (int i = 1; i <= n; i ++ ) {
    14.             for (int j = 1; j <= n; j ++ ) {
    15.                 g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
    16.             }
    17.         }
    18.     }
    19. }
    1. private static int kruskal() {
    2.     int res = 0;
    3.     int cnt = 0;
    5.     Arrays.sort(edges, 1, m + 1);
    7.     for (int i = 1; i <= n; i ++ ) {
    8.         p[i] = i;
    9.     }
    11.     for (int i = 1; i <= m; i ++ ) {
    12.         int u = edges[i].u;
    13.         int v = edges[i].v;
    14.         int w = edges[i].w;
    15.         int f1 = find(u);
    16.         int f2 = find(v);
    17.         if (f1 != f2) {
    18.             p[f1] = f2;
    19.             res += w;
    20.             cnt ++ ;
    21.         }
    22.     }
    24.     if (cnt < n - 1) {
    25.         return INF;
    26.     }
    27.     return res;
    28. }
    30. private static int find(int x) {
    31.     return (x == p[x]) ? x : (p[x] = find(p[x]));
    32. }
    34. class node implements Comparable<node> {
    35.     public int u;
    36.     public int v;
    37.     public int w;
    39.     node(int u, int v, int w) {
    40.         this.u = u;
    41.         this.v = v;
    42.         this.w = w;
    43.     }
    45.     @Override
    46.     public int compareTo(node o) {
    47.         return Integer.compare(w, o.w);
    48.     }
    49. }