## 《算法》读书笔记 - 并查集

union find 即 并查集 算法是在本书的 1.5 节中作为一个样例来学习的，可知其是非常基础的一种算法，本书给出了三种实现。

### 1. quick-find 算法 O(N^2)

即把主要工作放到 union 中完成，以 hdu OJ 1232 为例

union find 即 并查集 算法是在本书的 1.5 节中作为一个样例来学习的，可知其是非常基础的一种算法，本书给出了三种实现。

即把主要工作放到 union 中完成，以 hdu OJ 1232 为例

POJ 3393

Lucky and Good Months by Gregorian Calendar

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 1159 Accepted: 354

Description

Have you ever wondered why normally an year has 365 days, not 400 days? Why August have 31 days, but February have only 28 days? Why there are 7 days, not 6 days, in a week? Do people in ancient time use the same calendar as we do? There are many interesting conjectures and theories about those problems. Now we will tell you one story that may help explaining plausible answers to these questions. Using information in the story, you are then ask to solve an interesting problem using computer. Note that there are many theories about the calendar system discussed. This problem set will tell only one of them in a simplified way.

Throughout history, people keep track of time by observing the relative positions of the earth, the moon and the sun. A day is the amount of time the earth completes a self rotation. An year is defined to be the amount of time the earth orbits the sun. The earth takes roughly 365.242190 days to orbit the sun with some small variations. For practical purpose, a calendar year needs to have an integral number of days. Hence people need to add leap days to keep the calendar synchronized with the sun. If you keep a calendar year to have 365 years, you need to add one more day in a leap year roughly about every 4 years. However, this kind of calendar will not be in perfect synchronization with the earth’s position orbiting the sun because it advanced 365.25 days in average, which is slightly more than the actual period.