codeforces 445B DZY Loves Chemistry

1228 ワード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.text.DecimalFormat;

public class CF445B {

	static int[] f = new int[51];

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] nm = in.readLine().split(" ");
		int n = Integer.parseInt(nm[0]);
		int m = Integer.parseInt(nm[1]);
		for (int i = 1; i <= n; i++) {
			f[i] = i;
		}
		if (m == 0) {
			System.out.println(1);
			return;
		}
		int k = 0;
		for (int i = 0; i < m; i++) {
			String[] xy = in.readLine().split(" ");
			int x = Integer.parseInt(xy[0]);
			int y = Integer.parseInt(xy[1]);
			union(x, y);
		}
		double result = 1;
		for (int i = 1; i <= n; i++) {
			if (find(i) == i) {
				k++;
			}
		}
		int ans = n - k;
		result = Math.pow(2, ans);
		DecimalFormat decimalFormat = new DecimalFormat("#");
		System.out.println(decimalFormat.format(result));
	}

	private static int find(int x) {
		return x == f[x] ? x : find(f[x]);
	}

	private static void union(int x, int y) {
		int f1 = find(x);
		int f2 = find(y);
		if (f1 != f2) {
			f[f2] = f1;
		}
	}
}