codevs1955光纤通信（并查集）

/*

第一眼以为就是个区间覆盖

然后敲完提交60分0.0  然而觉得自己的做法很对

以为数据错了 后来发现XXX他的牛棚是一圈（牛过得挺好的啊 还能赏湖...）

然后枚举断开的点 可惜n=750 p=10000 这组数据TLE了 1.3秒的样子 90分

后来看题解说可以并查集 觉得好有道理的样子 0.0

下面是两次的代码

*/

#include<iostream>

#include<cstdio>

#include<algorithm>

#define maxn 10010

using namespace std;

struct node

{

    int l,r;

}boy[maxn];

int cmp(const node &x,const node &y)

{

    if(x.l==y.l)return x.r<y.r;

    return x.l<y.l;

}

int n,p,k,ans,minn=;

int main()

{

    scanf("%d%d",&n,&p);

    int x,y;

    for(int i=;i<=p;i++)

      {

          scanf("%d%d",&x,&y);

        boy[i].l=x;boy[i].r=y;

      }

    for(k=;k<=n;k++)

    {

        ans=;

        for(int i=;i<=p;i++)

          {

              if(boy[i].l<k)boy[i].l+=n;

              if(boy[i].r<k)boy[i].r+=n;

              if(boy[i].l>boy[i].r)swap(boy[i].l,boy[i].r);

          }

        sort(boy+,boy++p,cmp);

        int ri=boy[].r,li=boy[].l;

        for(int i=;i<=p;i++)

          if(boy[i].l>ri)

            {

              ans=ans+ri-li;

               li=boy[i].l;

              ri=boy[i].r;

             }

          else ri=max(ri,boy[i].r);

        ans=ans+ri-li;

        minn=min(minn,ans);

    }

     printf("%d",minn);

    return ;

}

/*

并查集

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 10010

using namespace std;

int fa[maxn],l[maxn],r[maxn],n,p,ans,Ans=;

int find(int x)

{

    if(x!=fa[x])fa[x]=find(fa[x]);

    return fa[x];

}

void unionn(int x,int y)

{

    if(x>y)swap(x,y);

    for(int i=x;i<y;i++)

      if(find(i)!=find(i+))

          {

            ans++;

            fa[find(i)]=find(i+);

        }

}

int main()

{

    cin>>n>>p;

    for(int i=;i<=p;i++)

      cin>>l[i]>>r[i];

    for(int k=;k<=n;k++)

      {

          ans=;

          for(int i=;i<=n*;i++)fa[i]=i;

          for(int i=;i<=p;i++)

            {

              int tmp1=l[i],tmp2=r[i];

            if(tmp1<k)tmp1=tmp1+n;

            if(tmp2<k)tmp2=tmp2+n;

            if(find(tmp1)!=find(tmp2))unionn(find(tmp1),find(tmp2));

          }

        Ans=min(Ans,ans);

      }

    cout<<Ans;

    return ;

}