poj1182：食物链题解

2024-07-16 07:25| 来源: 网络整理| 查看: 265

poj1182：食物链

听说是poj中最经典的一道并查集题目。我一做，果然很经典呢！好难啊！！！真的琢磨了很久才弄懂。这道题的重点就在于怎么用并查集表示题目中的关系环。

1. 题干

原题传送门1

原题传送门2

2. 思路详解

实际上，在做这道题之前，我对并查集的了解就只停留在权重选择和压缩路径上。也就是大家司空见惯的那种模板。顺带再默写一遍复习一下：

#include using namespace std; class unionfind { public: vector id, rank; void init(int n){ id.clear(); rank.clear(); id.resize(n + 1); id.assign(n + 1, 1); for (int i = 0; i while (id[i] != i){ id[i] = id[id[i]]; i = id[i]; } return i; } void Union(int id1, int id2){ id1 = find(id1); id2 = find(id2); if (rank[id1] > rank[id2

【本文地址】

公司简介

联系我们

poj1182：食物链 题解

poj1182：食物链题解