Shulou(Shulou.com)06/01 Report--

This article mainly explains "how to understand the database and search collection". Interested friends might as well take a look at it. The method introduced in this paper is simple, fast and practical. Next, let the editor take you to learn how to understand the database and search the collection.

And check the collection

And search set is considered by many to be one of the most concise and elegant data structures, which is mainly used to solve the problem of grouping some elements. For example, the Kruskal algorithm in the minimum generated graph uses this knowledge point. It manages a series of disjoint collections and supports two operations:

Union: merges two disjoint sets into one set.

Query (Find): queries whether two elements are in the same collection.

Of course, this definition is too academic, after reading it, I am afraid I will not be able to understand its specific use. So let's first take a look at and collect one of the most direct application stories: the quack school. After reading the story and checking the collection, you will know it.

The story will

There are all kinds of warriors scattered on the rivers and lakes, there are thousands of them. They don't have any legitimate jobs, and they walk around with swords on their backs all day. When they encounter that they are not like themselves, they will inevitably get into a fight. But one of the advantages of heroes is that they are loyal and never hit their friends. And they believe that "a friend of a friend is my friend". As long as it can be connected through a friend relationship, no matter how many turns, they all think it is one of their own. In this way, a gang has been formed in the world, which is connected by the friendship between the two. People who are not in the same gang can never be connected through friends, so they can rest assured to fight to death. But how can two people who don't know each other belong to the same circle of friends?

We can elect a more famous person in each circle of friends as the representative of that circle. In this way, each circle can be named "Chinese compatriot team" and "American compatriot team".... as long as the two people face each other whether their captain is the same person, they can determine the relationship between friends and enemies.

But there are still problems, ah, warriors only know who their direct friends are, and many people simply do not know the captain at all. if they want to judge who their captain is, they can only ask aimlessly through the friend's friend relationship: "are you the captain?" are you the captain? " In this way, if you want to fight, you have to ask for decades. I am so hungry that I can't stand it. In this way, the captain can not keep up face, not only the efficiency is too low, but also may fall into an infinite cycle. So the captain ordered the team to be reorganized. All the people in the team implement a hierarchical system to form a tree structure. My captain is the root node, and below are the second-level and third-level members respectively. Everyone just needs to remember who their superiors are. When judging enemies and friends, as long as you ask layers up to the highest level, you can determine who the captain is in a short time. Since all we care about is whether the two people are in a gang, it doesn't matter how they are connected through friendship, what the internal structure of each circle is, or even who the captain is. So we can let the captain reorganize the team at will, as long as we don't make a mistake about the relationship between friends and enemies. As a result, the school came into being.

The introduction of theoretical derivation and search set

The important idea of checking a set is to use an element in the set to represent the set. I have seen an interesting analogy in which the collection is compared to a gang and the representative element is the master. Next, let's use this metaphor to see and find out how the set works.

At first, all the heroes fought on their own. Of course, their respective masters are themselves. (for a collection with only one element, it means that the element is naturally the only element.)

Now, if No. 1 wins the match between No. 1 and No. 3 (it doesn't matter who wins here for the time being), then No. 3 will recognize No. 1 as the master (merge the collection of No. 1 and No. 3, and No. 1 is the representative element).

Now No. 2 wants to compete with No. 3 (merge the collection of No. 3 and No. 2), but No. 3 means, don't fight with me, let my master take care of you (merge represents elements). Might as well assume that No. 1 wins this time, then No. 2 also recognizes No. 1 as the master.

Now let's assume that there has also been a gang merger on the 4th, 5th and 6th, and the situation is as follows:

Now suppose No. 2 wants to compete with No. 6, as just said, call Master No. 1 and No. 4 to come out for a fight (Master really hard). After the victory on the 1st, No. 4 recognized No. 1 as the master, and of course his men also surrendered.

All right, the metaphor is over. If you have a little graph theory foundation, I believe you have noticed that this is a tree-like structure. To find the representative elements of the set, you only need to go up to the parent node (the circle pointed to by the arrow in the picture). Direct access to the root node of the tree (the orange circle in the picture). The parent of the root node is itself. We can just draw it as a tree:

In this way, we can write the simplest version and look up the code.

Initialize int fa [MAXN]; void init (int n) {for (int I = 1; I)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.