hdu3635Dragon Balls 并查集

时间：2015-07-20 23:32:45 阅读：157 评论：0 收藏：0 [点我收藏+]

//n个龙珠，在n个城市
//T a b 将包含a的所有龙珠移到b处
//Q a
//龙珠a在哪个城市，这个城市有多少龙珠，龙珠a移动了多少次
//并查集记录所有龙珠
//对于移动的次数在find更新的时候优化一下就行
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std ;
const int maxn = 10010 ;
int F[maxn] ;
int sum[maxn] ;
int time[maxn] ;
int find(int x)
{
int r = x ;
int sum_b = 0 ;
int res = 0 ;
while(r!=F[r])
{
sum_b += time[r] ;
r = F[r] ;
}
int i = x ;
while(F[i] != r)
{
int j = F[i] ;
F[i] = r ;
int t = time[i] ;
time[i] = sum_b - res ;
res += t;
i = j ;
}
return r ;
/*if(x == F[x])return F[x] ;
int t = F[x] ;
F[x] = find(F[x]) ;
time[x] += time[t] ;
return F[x];*/
}
void join(int a, int b)
{
int fx = find(a) ;
int fy = find(b) ;
if(fx != fy)
{
time[fx] = 1 ;
F[fx] = fy ;
sum[fy] += sum[fx] ;
sum[fx] = 0 ;
}
}
int main()
{
//freopen("in.txt" ,"r" , stdin) ;
int T ;int cas = 0 ;
scanf("%d" , &T) ;
while(T--)
{
int N , Q ;
scanf("%d%d" , &N , &Q) ;
for(int i = 1;i <= N;i++)
F[i] = i ,sum[i] = 1;
memset(time , 0 , sizeof(time)) ;
printf("Case %d:\n" ,++cas) ;
char ch ;int a ,b ;
for(int i = 1;i <= Q ;i++)
{
scanf("%c%c" , &ch,&ch ) ;
if(ch == ‘T‘)
{
scanf("%d%d" , &a , &b) ;
join(a , b) ;
}
else if(ch == ‘Q‘)
{
scanf("%d" , &a) ;
int fx = find(a) ;
printf("%d %d %d\n" ,fx , sum[fx] , time[a]) ;
}
}
}
return 0 ;
}

原文：http://blog.csdn.net/cq_pf/article/details/46974805

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)