首页 > 其他 > 详细

POJ 1988

时间:2015-06-10 17:15:04      阅读:169      评论:0      收藏:0      [点我收藏+]
#include<iostream>
#include<stdio.h>
#include<algorithm>
#define MAXN 30005
using namespace std;


int place[MAXN];
int up[MAXN];
int pre[MAXN];


void init()
{
    int i;
    for(i = 0; i < MAXN; ++ i)
    {
        pre[i] = i;
        up[i] = 0;
        place[i] = 1;
    }
}

int find_pre(int s)
{
    int k;
    k = pre[s];
    if(k != s)
    {
        pre[s] = find_pre(k);
        up[s] += up[k];
    }
    return pre[s];
}

void comb(int a,int b)
{
    a = find_pre(a);
    b = find_pre(b);
    pre[b] = a;
    up[b] = place[a];
    place[a] += place[b];
}

int main()
{
    //freopen("acm.acm","r",stdin);
    int p;
    int i;
    int j;
    int t;
    int a;
    int b;
    char c;
    init();
    scanf("%d",&p);
    for(t = 0; t < p; ++ t)
    {
        cin>>c;
        if(c == M)
        {
            scanf("%d%d",&a,&b);
            ///-- a;
            //-- b;
            comb(a,b);
        }
        if(c == C)
        {
            scanf("%d",&a);
            //-- a;
            b = find_pre(a);
            cout<<place[b] - up[a] - 1<<endl;
        }
    }
    
}

 

POJ 1988

原文:http://www.cnblogs.com/gavinsp/p/4566599.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!