校门外的树 （C++代码）------两种解法，复杂点的“并查集”和简单的“数组标记”

对于这道题有鄙人这里陈述两种解法******
第一种复杂，第二种简单，没学过并查集的同学可以看第二种。
第一种是“并查集”，这种解法有点复杂，“并查集的思想”是把相互之间有关系的元素放在不同的集合，它的思路可以区分不同的元素，而这道题对于不同的元素可以理解为，不同的区间。题目中不是说输入M行，每行两个数据吗，这两个数据其实可以看成一个区间，接下来就运用并查集的思想，把区间相互重叠的放在一个集合，注意：比如3个区间，[10,30],[20,40],[35,50],这三个区间也是一个集合的，他们虽然没有彼此之间有联系，但是你画在纸上你就发现他们还是重叠在一条线上。另外要处理一下，如果这两个区间有联系，比如A的区间为[30,50],B的区间为[40,80],那么他们就放在同一集合，而且他们的区间都要变成[30,80]。
###没学过并查集的同学，可以在百度上搜一下哦，不然看第一种解法是看不懂的，但是第一种解法它的空间和时间上都是很优的，比用数组标记啊要快很多
第二种解法很简单，这就是数组标记，这种思路在很多题是可以用的，这是一种很重要的思想，听学长说他在面试的时候用到了
这种思路在这道题是这样的，开一个数组d[ ],开始时所有值都是0,接下来，如果 i 这个位置在公路上，那么d[ i ]=1，然后统计一下d[i]==1的个数，就是要被砍掉的数的数量，那么剩下的就可以求了，或者统计d[i]==0的个数，就是剩下的树的棵数
/*#include<iostream>
using namespace std;
#define N 1005
struct node{
    int x;
    int y;
    int e;
}f[N];
int L,M;
int max( int a,int b ){
    return a>b ? a:b;
} 
int min( int a,int b ){
    return a>b ? b:a;
} 
void Init_(  ){
    int i,j;
    for(i=1;i<=M;i++){
        f[i].e=i;
    }
    return ;
}
int getf( int v ){
    if( f[v].e==v )
    return v;
    else{
        f[v].e=getf( f[v].e );
        return f[v].e;
    }
}
void merge_(  int a,int b ){
    int t1,t2;
    t1=getf( a );
    t2=getf( b );
    if( t1!=t2 ){
        f[t2].e=t1;
    }
    f[t1].x=min( f[t1].x,f[t2].x );
    f[t1].y=max( f[t1].y,f[t2].y );
    f[t2].x=min( f[t1].x,f[t2].x );
    f[t2].y=max( f[t1].y,f[t2].y );
}
int ok( int a,int b,int c,int d ){   //这个函数是判断两个区间是否重叠
    if( c<=b&&a<=c )
    return 1;
    if( a<=d&&c<=a )
    return 1;
    return 0;
}
int main( ){
    int i,j;
    cin>>L>>M;
    for(i=1;i<=M;i++){
        cin>>f[i].x>>f[i].y;
    }
    Init_( );
    for(i=1;i<=M;i++){
        for(j=i+1;j<=M;j++){
            if( ok( f[i].x,f[i].y,f[j].x,f[j].y ) )
            merge_( i,j );
        }
    }
    long sum=0;
    for(i=1;i<=M;i++){
        if( f[i].e==i )
        sum+=f[i].y-f[i].x+1;
    }
    cout<<L+1-sum<<endl;
    return 0;
}*/
//############################第二种解法如下
#include<iostream>
using namespace std;
#define N 10005
int main(){
    int i,j,k,sum=0;
    int L,M,x,y;
    cin>>L>>M;
    int d[N]={0};
    for(i=1;i<=M;i++){
        cin>>x>>y;
        for(j=x;j<=y;j++)
        d[j]=1;  //区间[x,y]就是公路要经过的，所以这个范围的树要被砍，所以d[i]=1
    }
    for(i=0;i<=L;i++){
        if( d[i]!=1)
        sum++;
    }
    cout<<sum<<endl;
    return 0;
}