存档

文章标签 ‘路径压缩’

POJ 1161 The Suspects[并查集]

2011年9月13日 2 条评论

并查集分三个操作,并、查、初始化。初始化时把秩初始化为0,值和父亲都是自己;查的时候看看节点的父亲是不是自己,如果是,则停止查找,如果不是,查找父节点的父节点,同时压缩路径,把子孙节点的父节点都更新为最后找到的父节点。并的时候判断下两个节点是不是在一个集合中,如果不在,判断两个节点的父节点的秩,秩大的做父节点。如果秩相等,则任意一个节点作为父节点,作为父节点的秩增加1.
传送题目地址:POJ 1161 The Suspects http://poj.org/problem?id=1611

1
[......]

继续阅读