uva 10608 FRIENDS

순전히 고찰하고 수집하는 것은 고전적인 문제라고 할 수 있다.하나의 집합 중 몇 개의 원소가 있는지 통계한 후에 원소의 개수가 가장 많은 집합을 찾다
그냥 합쳐서 모으면 넘길 수 있어요.
그리고 압축 경로를 따로 썼는데 시간이 바뀌지 않을 줄은 몰랐다
그리고 하나 더 쓰세요. 시간은 변하지 않았어요. 그래요......
기본적인 병집만 알면 코드는 문제가 되지 않고 누드적으로 병집할 뿐이다
 
코드 1: 순수

#include <cstdio>

#include <cstring>

#define N 30000

int p[N],c[N];

int n,m;



int find(int x)

{ return p[x]==x ? x : p[x]=find(p[x]);  }



int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

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

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

        { p[i]=i; c[i]=0; }



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

        {

            int x,y,u,v;

            scanf("%d%d",&u,&v);

            x=find(u);

            y=find(v);

            if(x!=y)

                p[x]=y;

        }



        for(int i=1; i<=n; i++)  //                       

        {

            int x=find(i);

            c[x]++;

        }

        int max=0;

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

            if(c[i]>max)

                max=c[i];



        printf("%d
",max);

    }

    return 0;

}

 
코드 2: 압축 경로

#include <cstdio>

#include <cstring>

#define N 30000

int p[N],c[N];

int n,m;



int find(int x)  //   

{

    int i=x,r=x,j;

    while(r!=p[r])

        r=p[r];

    while(i!=r)  //    

    {

        j=p[i];  //    i   

        p[i]=r;  //  i          

        i=j;     //          

    }

    return r;

}



int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

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

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

        { p[i]=i; c[i]=0; }



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

        {

            int x,y,u,v;

            scanf("%d%d",&u,&v);

            x=find(u);

            y=find(v);

            if(x!=y)

                p[x]=y;

        }



        for(int i=1; i<=n; i++)  //                       

        {

            int x=find(i);

            c[x]++;

        }

        int max=0;

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

            if(c[i]>max)

                max=c[i];



        printf("%d
",max);

    }

    return 0;

}

 
코드3: 통계 집합 요소의 방법을 다시 수정합니다

#include <cstdio>

#include <cstring>

#define N 30000

int p[N],c[N];

int n,m;



int find(int x)  //   

{

    int i=x,r=x,j;

    while(r!=p[r])

        r=p[r];

    while(i!=r)  //    

    {

        j=p[i];  //    i   

        p[i]=r;  //  i          

        i=j;     //          

    }

    return r;

}



int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

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

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

        { p[i]=i; c[i]=1; }



        int max=0;

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

        {

            int x,y,u,v;

            scanf("%d%d",&u,&v);

            x=find(u);

            y=find(v);

            if(x!=y)

            {

                p[x]=y;

                c[y]+=c[x];

                if(c[y]>max)

                    max=c[y];

            }

        }

        printf("%d
",max);

    }

    return 0;

}

 
 
비극, 시간은 본질적으로 향상되지 않는구나......