UVA 11987 Almost Union-Find

그리고 집합 을 찾 아서 할 수 있 습 니 다. 단지 기술 이 필요 합 니 다. 어제 썼 는데 문제 가 있 습 니 다. 합병 하면 비교적 간단 합 니 다. 그들 이 집합 한 각 값 을 직접 합병 하면 됩 니 다. 그러나 p 를 이동 할 때 문제 가 있 습 니 다. parents [p] 가 p 와 같 지 않 을 때 문제 가 없습니다. 그러나 p 가 parents [p] 와 같 으 면 문제 가 있 습 니 다. p 를 옮 기 면...그러면 parents [q] = p 의 노드 를 찾 으 면 문제 가 발생 합 니 다.나 는 오랫동안 생각 했 지만 좋 은 방법 이 생각 나 지 않 았 다. 오늘 다른 소 협 에 게 물 어 보 니 좋 은 생각 을 얻 었 다. 바로 모든 점 에 가상 parents 를 설치 하 는 것 이다. 이 parents 는 옮 겨 가지 않 을 것 이다. 그러면 업 데 이 트 를 하면 거 리 낌 이 없고 고 친 후에 바로 A 가 떨어진다.과연 대중의 힘 은 비 할 바 없 이 강대 하 다.
 
코드:
 

#include <iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
const int maxn=200000+10;
const int base=100000;
int parents[maxn],sum[maxn],num[maxn];
int Find(int x)
{
    if(x!=parents[x])
    {
        parents[x]=Find(parents[x]);
    }
    return parents[x];
}
void Uion(int x,int y)
{
    int a=Find(x);
    int b=Find(y);
    if(a!=b)
    {
        parents[b]=a;
        sum[a]+=sum[b];
        sum[b]=0;
        num[a]+=num[b];
        num[b]=0;
    }
}
void Move(int x,int y)
{
    int a=Find(x);
    int b=Find(y);
    if(a!=b)
    {
        parents[x]=b;
        num[a]--;
        num[b]++;
        sum[b]+=x;
        sum[a]-=x;
    }
}
void Init(int n)
{
    for(int i=0;i<=n;++i)
    {
        parents[i]=i+base;
        parents[i+base]=i+base;
        sum[i+base]=i;
        num[i+base]=1;
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,m;
    while(cin>>n>>m)
    {
        Init(n);
        int type,p,q;
        for(int i=0;i<m;++i)
        {
            cin>>type;
            if(type==1)
            {
                cin>>p>>q;
                Uion(p,q);
            }
            else if(type==2)
            {
                cin>>p>>q;
                Move(p,q);
            }
            else
            {
                cin>>p;
                cout<<num[Find(p)]<<" "<<sum[Find(p)]<<endl;
            }
        }
    }
    return 0;
}