BOJ. Cycle game (20040)

Problem link

Process the edges in their input order. Before adding an edge (a, b), find the representative of each endpoint’s connected component in the graph formed by earlier edges. If the representatives are equal, a path already connects a and b, so adding this edge creates a cycle; report its one-based turn immediately. Otherwise, merge the two components. This detects the first cycle because a cycle is created exactly when an edge joins vertices already connected by a path. It also correctly detects a self-loop on its own turn and treats the second copy of a parallel edge as cycle-forming.

The disjoint-set union structure stores each root’s component size as a negative value. find applies path compression, and union attaches the smaller component below the larger one. Together they give amortized O(α(N)) time per operation, so processing M edges takes O(M α(N)) time and the structure uses O(N) space. The program prints 0 if no edge creates a cycle.

import java.io.*;

public class Main {
  static class FastScanner {
    private final InputStream input;
    private final byte[] buffer = new byte[1 << 16];
    private int length = 0;
    private int pointer = 0;

    FastScanner(InputStream input) {
      this.input = input;
    }

    private int read() throws IOException {
      if (pointer == length) {
        length = input.read(buffer);
        pointer = 0;
        if (length == -1) return -1;
      }
      return buffer[pointer++];
    }

    int nextInt() throws IOException {
      int c;
      do {
        c = read();
      } while (c <= ' ' && c != -1);

      int value = 0;
      while (c > ' ') {
        value = value * 10 + c - '0';
        c = read();
      }
      return value;
    }
  }

  static class DisjointSet {
    private final int[] parentOrSize;

    DisjointSet(int n) {
      parentOrSize = new int[n];
      for (int i = 0; i < n; i++) parentOrSize[i] = -1;
    }

    int find(int node) {
      if (parentOrSize[node] < 0) return node;
      return parentOrSize[node] = find(parentOrSize[node]);
    }

    boolean union(int a, int b) {
      int rootA = find(a);
      int rootB = find(b);
      if (rootA == rootB) return false;

      if (parentOrSize[rootA] > parentOrSize[rootB]) {
        int temp = rootA;
        rootA = rootB;
        rootB = temp;
      }
      parentOrSize[rootA] += parentOrSize[rootB];
      parentOrSize[rootB] = rootA;
      return true;
    }
  }

  public static void main(String[] args) throws IOException {
    FastScanner input = new FastScanner(System.in);
    int n = input.nextInt();
    int m = input.nextInt();
    DisjointSet dsu = new DisjointSet(n);

    for (int turn = 1; turn <= m; turn++) {
      int a = input.nextInt() - 1;
      int b = input.nextInt() - 1;
      if (!dsu.union(a, b)) {
        System.out.println(turn);
        return;
      }
    }

    System.out.println(0);
  }
}