UVA 11987 Almost Union - Find (편집 + 삭제)

n 개의 집합 을 시작 합 니 다. m 가지 작업, 초기 집합: {1}, {2}, {3}, {n} 작업 은 세 가지 가 있 습 니 다.
그리고 집합 을 찾 으 면 1 은 두 개의 집합 을 합 치 는 것 이 고 3 은 두 개의 가중치 를 기록 해 야 한다.조상의 가중치 만 있 으 면 Find 작업 은 가중치 업데이트 가 필요 하지 않 기 때문이다.그 다음 에 요 소 를 분리 하 는 것 입 니 다. 여기 서 저 는 매 핑 방법 을 사용 합 니 다. 처음에 모든 요소 가 자신 을 매 핑 했 습 니 다. 그 다음 에 요 소 를 삭제 하려 고 할 때 저 는 요 소 를 직접 삭제 하지 않 습 니 다. (삭제 하면 큰 영향 을 줄 수 있 기 때 문 입 니 다) 저 는 이 위 치 를 새로운 값 이 나타 날 수 없 도록 매 핑 했 습 니 다. 그러면 우 리 는 원래 의 집합 을 처리 합 니 다.새로운 값 을 사용 하여 현재 의 집합 을 유지 하면 됩 니 다. 앞으로 우 리 는 맵 의 값 만 볼 뿐 값 을 직접 삭제 하 지 는 않 았 지만 원래 의 값 은 사용 하지 않 습 니 다.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define eps 1E-8
/*        -0.000*/
#define Sgn(x) (x//x          ,      
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//     
#define zero(x) (((x)>0?(x):-(x))//      0
#define mul(a,b) (a<
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=1<<28;
const double Pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=200010;
int fat[Max],num[Max];
ll ran[Max];
int mp[Max],tot;//                
void Init(int n)
{
    for(int i=0;i<=n;i++)
    {
        fat[i]=i;
        ran[i]=(ll)i;
        num[i]=1;
        mp[i]=i;
    }
    tot=n+1;
    return;
}
int Find(int x)
{
    if(x==fat[x])
        return fat[x];
    return fat[x]=Find(fat[x]);
}
void Union(int x,int y,int typ)
{
    int prex=x;//        
    x=mp[x],y=mp[y];//    
    int x1=Find(x);
    int y1=Find(y);
    if(x1==y1)
    return;
    if(typ==1)
    {
    fat[x1]=y1;
    ran[y1]+=ran[x1];
    num[y1]+=num[x1];
    return;
    }
    mp[prex]=tot++;//    ，      ,  mp

    fat[mp[prex]]=y1;
    num[mp[prex]]=1;
    ran[mp[prex]]=(ll)x;

    num[x1]--;
    ran[x1]-=(ll)prex;

    num[y1]++;
    ran[y1]+=(ll)prex;
    return;
}
int main()
{
    int n,m;
    int typ,xx1,yy1;
    while(~scanf("%d %d",&n,&m))
    {
        Init(n);
        for(int i=0;iscanf("%d",&typ);
            if(typ==1)
            {
                scanf("%d %d",&xx1,&yy1);
                Union(xx1,yy1,1);
            }
            else if(typ==2)
            {
            scanf("%d %d",&xx1,&yy1);
            Union(xx1,yy1,2);
            }
            else
            {
                scanf("%d",&xx1);
                yy1=Find(mp[xx1]);
                printf("%d %lld
",num[yy1],ran[yy1]);
            }
        }
    }
    return 0;
}