HDU - 3461 Code Lock （并查集和幂运算）

题意：有一个字母锁，含有n个字母，然后给定m个区间，并规定区间里面的那一段字母是可以同时改变的，比如a变为b,b变为c,z变为a之类的，然后如果锁可以通过有限次变换变成相同的，就规定为同一把锁。然后要求有多少把不同的锁

思路：起初没想到好的处理有重叠的集合的情况，后来参考了学长的点击打开链接

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 10000005;
const int mod = 1000000007;

int f[MAXN];
int l,r,cnt;

int find(int u){
	if (u != f[u])
		f[u] = find(f[u]);
	return f[u];
}

void merge(int x,int y){
	int fx = find(x);
	int fy = find(y);
	if (fx != fy){
		f[fx] = fy;
		cnt++;
	}
}

long long func(int n,int m){
	long long sum;
	if (n == 0)
		return 1;
	sum = func(n/2,m);
	sum = (sum * sum) % mod;
	if (n & 1)
		sum = (sum * m) % mod;
	return sum;
}

int main(){
	int n,m;
	while (scanf("%d%d",&n,&m) != EOF){
		cnt = 0;
		for (int i = 0; i <= n; i++)
			f[i] = i;
		for (int i = 1; i <= m; i++){
			scanf("%d%d",&l,&r);
			merge(l-1,r);
		}
		printf("%lld\n",func(n-cnt,26)%mod);
	} 	
	return 0;
}

HDU - 3461 Code Lock （并查集和幂运算）,布布扣,bubuko.com

HDU - 3461 Code Lock （并查集和幂运算）

原文：http://blog.csdn.net/u011345136/article/details/21247961