Skip to content

Instantly share code, notes, and snippets.

@hiroshi-cl
Last active December 27, 2015 23:59
Show Gist options
  • Save hiroshi-cl/7410401 to your computer and use it in GitHub Desktop.
Save hiroshi-cl/7410401 to your computer and use it in GitHub Desktop.
2013年 模擬地区予選 Problem D: Everlasting -One- [Licence: NYSL Version 0.9982]
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static final int MOD = 1_000_000_007;
public static void main(final String... args) {
final Scanner sc = new Scanner(System.in);
main:
while (sc.hasNext()) {
final int N = sc.nextInt();
final int M = sc.nextInt();
if (N == 0 && M == 0)
return;
final UnionFind uf = new UnionFind(N);
for (int i = 0; i < M; i++)
uf.union(sc.nextInt() - 1, sc.nextInt() - 1);
final int cnt = uf.countComponents();
int ans = 1;
for (int i = 0; i < cnt; i++) {
ans <<= 1;
if (ans >= MOD)
ans -= MOD;
}
if (cnt < N) {
ans++;
if (ans >= MOD)
ans -= MOD;
}
System.out.println(ans);
}
}
public static class UnionFind {
final int[] tree;
UnionFind(final int size) {
tree = new int[size];
Arrays.fill(tree, -1);
}
int root(final int idx) {
return tree[idx] < 0 ? idx : (tree[idx] = root(tree[idx]));
}
boolean union(int x, int y) {
x = root(x);
y = root(y);
if (x == y)
return false;
if (tree[x] > tree[y]) {
final int tmp = x;
x = y;
y = tmp;
}
tree[x] += tree[y];
tree[y] = x;
return true;
}
int countComponents() {
int cnt = 0;
for (final int i : tree)
if (i < 0)
cnt++;
return cnt;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment