Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

【并查集】 so easy 附代码

Posted by WilliamACM at 2013-03-10 22:46:40 on Problem 1988
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N=30005;
int fa[N],son[N],dist[N];

int FA(int x)
{
    if(fa[x]==x) return x;
    int ans=FA(fa[x]);
    dist[x]+=dist[fa[x]];
    return fa[x]=ans;


}
void Union(int x,int y)
{
    int fax=FA(x);
    int fay=FA(y);
    if(fax==fay) return;
    fa[fax]=fay;
    dist[fax]=son[fay]+1;
    son[fay]+=son[fax]+1;
}
void init()
{
    for(int i=1;i<N;i++)
    fa[i]=i;
    int m;cin>>m;
    while(m--)
    {
        char ss[10];
        scanf("%s",ss);
        if(ss[0]=='M')
        {
            int s,t;
            scanf("%d %d",&s,&t);
            Union(s,t);
//            printf("%d : %d %d %d\n",s,FA(s),son[s],dist[s]);
//            printf("%d : %d %d %d\n",t,FA(t),son[t],dist[t]);
        }
        else
        {
            int x;scanf("%d",&x);
            FA(x);
            printf("%d\n",dist[x]);
        }
    }

}
int main()
{
   // freopen("in.txt","r",stdin);
    init();
//    cout << "Hello world!" << endl;
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator