题解 | #畅通工程#并查集模板题

import java.util.Scanner;
public class Main {
    private static int[] parents;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            if (n == 0) break;
            int m = sc.nextInt();
            parents = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                parents[i] = i;
            }
            while (m-- > 0) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                if (find(x) != find(y)) {
                    parents[find(x)] = find(y);
                }
            }
            int ans = 0;
            for (int i = 1; i <= n; i++) {
                if (find(i) == i) {
                    ans++;
                }
            }
            System.out.println(ans - 1);
        }
    }
    private static int find(int x) {
        return x == parents[x] ? x : (parents[x] = find(parents[x]));
    }
}