• [[Union-Find]]


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45



import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int[] root;

	static void init() {
		for (int i = 1; i <= N; i++)
			root[i] = -1;
	}

	static int find(int x) {
		if (root[x] < 0) return x;
		return root[x] = find(root[x]);
	}

	static void union(int x, int y) {
		int xRoot = find(x);
		int yRoot = find(y);
		if (xRoot == yRoot) return;

		root[xRoot] += root[yRoot];
		root[yRoot] = xRoot;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(in.readLine());
		root = new int[N+1];
		init();

		int M = Integer.parseInt(in.readLine());
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			union(x, y);
		}
		System.out.println(-root[find(1)] - 1);
	}
}