HDU - 3461 Code Lock （並查集和冪運算）

題意：有一個字母鎖，含有n個字母，然後給定m個區間，並規定區間裡面的那一段字母是可以同時改變的，比如a變為b,b變為c,z變為a之類的，然後如果鎖可以通過有限次變換變成相同的，就規定為同一把鎖。然後要求有多少把不同的鎖

思路：起初沒想到好的處理有重疊的集合的情況，後來參考了學長的點擊打開鏈接

#include 
#include 
#include 
#include 
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;
}