事实上路径压缩也能够不用.............

题目的大意：

一个password锁上有编号为1到N的N个字母，每一个字母能够取26个小写英文字母中的一个。再给你M个区间[L,M]。表示该区间的字母能够一起同步“添加”（从'a'变为'b'为增1。'z'增1为'a'）。假如一组password依照给定的区间进行有限次的“添加”操作后能够变成还有一组password，那么我们觉得这两组password是同样的。该题的目标就是在给定N、M和M个区间的前提下计算有多少种不同的password。



     依据题意，假设一个可调整的区间都没有的话，答案应该是26的N次方。每当增加一个区间的时候。答案就降低为之前的26分之1（由于该区间的增加使得原本不同的26种情况变得等价了）。因此当有x个“不同的”区间增加进来之后，答案应该为26^(N-x)。

可是另一些特殊情况须要考虑。一个是相同的区间反复增加是不会改变答案的，这点比較好理解。

另一点是假设一个区间能够由其它若干个区间“拼接”而得到，那么它的增加不能改变答案。比如假设已经有了区间[1,3]和[4,5]。那么再增加区间[1,5]答案也不会改变，由于[1,5]所能实现的password变化全都能够由同步运行[1,3]与[4,5]来实现，也就是[1,3]+[4,5]等价于[1,5]。特别要注意的是[1,3]+[3,5]这样的情况并不等价于[1,5]。

思路：

所以题目就是求区间的个数了。可是注意的是 【1，3】【4，5】和【1，5】区间是等价的。【1。3】【3，5】和【1。5】又是不等价的的。由于3是重叠的。

怎样解决区间个数，用并查集刚好，只是要变化的是merge_set（l-1，r）或者merge_set【l。r+1】这样能够解决，线段的拼接问题。这里要好好想一下。

怎样求区间：

并查集， merge_set（l-1,r) or  merge_set( l,r+1)，这里要好好想一下。通过+1，-1刚好连接上了端点，不是吗？

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#define mod 1000000007

#define N 10000000+10

using namespace std;

typedef long long int64;

int uset[N];

//int rank[N];

int cnt;

void make_set(int n)

{

    for(int i=0;i<=n;i++)

    {

        uset[i]=i;

        //rank[i]=1;

    }

}

int find_set(int x)

{

    if(uset[x]!=x)

        uset[x]=find_set(uset[x]);

    return uset[x];

}

void merge_set(int x,int y)

{

    int fx=find_set(x);

    int fy=find_set(y);

    if(fx==fy)

        return;

    else

    {

        uset[fx]=fy;

        cnt++;

    }

}

int64 exp(int n)

{

    int64 res=1;

    int64 tmp=26;

    while(n)

    {

        if(n&1)

            res=(res*tmp)%mod;

        tmp=tmp*tmp%mod;

        n>>=1;

    }

    return res;

}

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        make_set(n);

        cnt=0;

        for(int i=0;i<m;i++)

        {

            int l,r;

            scanf("%d%d",&l,&r);

            merge_set(l-1,r);

        }

        //printf("-->%d\n",n-cnt);

        printf("%I64d\n",exp(n-cnt));

    }

    return 0;

}