注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

石门实验中学卢凯宾的博客

向前跑,迎着冷眼和嘲笑。

 
 
 

日志

 
 

洛谷1551 -- 亲戚  

2015-12-27 13:28:03|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题意:有N个人和M个亲戚关系,规定若i是j的亲戚则i的所有亲戚都是j的亲戚。有P次询问某两人是否具有亲戚关系。
分析:具有亲戚关系的人都在同一个集合里,符合并查集的性质。本题数据范围不大,N<=5000,可以不用优化。
代码:
# include <cstdio>

const int SIZE=5000+5;

int n , m , p , f[SIZE] ;

int _find ( int ) ; //求集合的根
void _union ( int , int ) ; //合并两个集合

int main () {
	scanf ( "%d%d%d" , &n , &m , &p ) ;
	for ( int i=0 ; i!=n+1 ; ++i ) f[i]=i ; //初始化
	for ( int i=0 ; i!=m ; ++i ) {
		int A , B ;
		scanf ( "%d%d" , &A , &B ) ;
		_union ( A , B ) ;
	}
	for ( int i=0 ; i!=p ; ++i ) {
		int A , B ;
		scanf ( "%d%d" , &A , &B ) ;
		if ( _find(A)==_find(B) ) printf ( "Yes\n" ) ; else printf ( "No\n" ) ;
	}
	return 0 ;
}

int _find ( int i ) {
	return f[i]==i ? i : ( f[i]=_find(f[i]) ) ;
	//是根就返回自己,否则路径压缩
}

void _union ( int i , int j ) {
	int fi=_find(i) ;
	int fj=_find(j) ;
	if ( fi!=fj ) f[fi] = fj ; //不在同一集合中才合并
	return ;
}

  评论这张
 
阅读(7)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018