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

And checking the collection is a trick I learned from the master during the summer vacation. I think it's really an exquisite design. A kind of problem that I couldn't solve before can be solved in such a simple and efficient way. I'm sorry party didn't share it. Party: shit, what do I care? Do I know you well? )

Let's take a look at an example, Hangzhou Electric Power 1232 unimpeded Project.

First of all, I will give you several towns on the map, all of which can be seen as points, and then tell you which pairs of towns are directly connected by roads. Finally, the problem of connectivity of the whole picture should be solved. For example, randomly give you two points to determine whether they are connected, or ask you how many connected branches there are in the whole picture, that is, they are divided into independent blocks. For example, the question of the smooth flow project, asking how many more roads need to be built, is essentially asking for how many connected branches. If it is a connected branch, it means that the points on the whole picture are connected and there is no need to build the road; if it is two connected branches, just build one more road, choose one point from each of the two branches, and connect them. Then all the points are connected; if there are three connected branches, just build two more roads.

This is illustrated by the following set of data input data

4 2 1 3 4 3

The first line tells you that there are four points and two roads. The next two lines tell you that there is a road between 1 and 3 and a road between 4 and 3. Then the whole picture is divided into 1-3-4 and 2 parts. As long as you add one more path, connect 2 with any other point, and the smooth flow project is realized, then the output result of this set of data is 1. All right, now program to achieve this function, there are hundreds of towns, I do not know how many roads, and there may be circuits. What can I do about this?

I didn't know it before. Since I used it and checked the collection, hey, the effect is really good! My whole family uses it!

The lookup set consists of an array of integers and two functions. The array pre [] records what the leading point of each point is, the function find is to find, and join is to merge.

Int pre [1000]

Int find (int x) / / find the root node

{

Int rystx

While (pre [r]! = r) / / returns the root node r

R=pre [r]

Int iTunx, j

While (I! = r) / / path compression

{

J = pre [I]; / / record his value with the temporary variable j before changing the superior

Pre [I] = r; / / change the superior to the root node

IStij

}

Return r

}

Void join (int xreint y) / / determine whether x y is connected or not

/ / if it's connected, don't worry about it / / if it's not connected, merge the connected branches where they are located.

{

Int fx=find (x), fy=find (y)

If (fxpurify)

Pre [fx] = fy

}

In order to explain and check the principle of collection, I will give a more loving example. It is said that there are all kinds of warriors scattered in 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 community is formed in the rivers and lakes, which is connected by the friendship between the two. On the other hand, people who are not in the same community can not be connected by 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 choose a more famous person in each circle of friends as the representative of that circle, so that each circle can be named "Zidane's team of friends" and "Ronaldo's team of friends". As long as the two people face each other whether their captain is the same person, they can determine the relationship between friends and foes.

But there are still problems, ah, the heroes only know who their direct friends are, and many people don't know the captain at all. To judge who their captain is, they can only ask aimlessly through the friends' relationship: "are you the captain? are you the captain?" In this way, the captain can not save face, and the efficiency is too inefficient, 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 two people are connected, it doesn't matter how they are connected, 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.

Http://i3.6.cn/cvbnm/6f/ec/f4/1e9cfcd3def64d26ed1a49d72c1f6db9.jpg

Let's look at and check the implementation of the set. Int pre [1000]; this array records who is the superior of each warrior. Heroes are numbered from 1 or 0 (depending on the meaning of the topic). Pre [15] = 3 means that the superior of the 15th warrior is the 3rd warrior. If a person's superior is himself, that means he is in charge, and the search ends here. There are also those who are alone, such as Ouyang Feng, then his superior is himself. Everyone only recognizes his or her superiors. For example, Hu Qingniu only knows that his superior is Yang Zuo. Who is Zhang Wuji? Don't know! If you want to know who your boss is, you can only check it up at one level. Find this function is used to find the palm door, the meaning couldn't be clearer (forget the path compression algorithm, we'll talk about it later).

Int find (int x) / / find the boss of my (x)

{

Int rnsx; / / entrust r to find the boss.

While (pre [r]! = r) / / if the superior of r is not r himself (that is to say, the hero found is not the master = =)

R=pre [r] / / r went on looking for his superior until he found the boss.

Return r; / / the palm door is driving to ~ ~

}

Let's take a look at the join function, which connects a line between two points, so that all the points of the two plates where they used to be can communicate with each other. This is easy to do in the picture, just draw a line. But now we use search sets to describe the situation in martial arts, there is only one pre [] array, how to achieve it? As an example, suppose the current situation in the martial arts forest is shown in the picture. Xuzhu Little Monk and Zhou Zhiluo MM are two characters I like very much, and their ultimate boss are Abbot Xuanci and exterminator too, which are obviously two camps. I didn't want them to fight each other, so I said to them, "you two pull the hook and be good friends." For my sake, they agreed. This consent is no small matter, the whole Shaolin and Emei people can not fight. How can such a great change be realized and how many changes will be made? In fact, it was very simple. I said to Abbot Xuan ci, "Master, please change your superior to the exterminator. In this way, the ultimate boss of all the original members of the two factions is Shi Tai, so let's play a ball! anyway, all we care about is connectivity, and the internal structure of the faction doesn't matter." Xuanci must have been furious when he heard this: "Damn it, why did I become her employee? why not the other way around? I protest!" The protest is null and void. God arranged it, the biggest. Anyway, whoever joins will have the same effect, so I randomly designated one. Is it clear what this function means?

Void join (int xreint y) / / I want Xu Zhu and Zhou Zhi Ruo to be friends.

{

Int fx=find (x), fy=find (y); / / the boss of Xuzhu is Xuanchi, and the boss of MM is extinction.

If (fxpurify) / / Xuanchi and extinction are obviously not the same person.

Pre [fx] = fy; / / the abbot had to be the subordinate of the division aggrieved.

}

Let's look at the path compression algorithm. The process of establishing a school is connected by two people with the join function, and who works for whom is completely random. I can't predict what the final tree-like structure will become, and it's possible to be a long snake. In this way, the efficiency of the search will be relatively low. The ideal situation is that all people's direct superiors are in charge, and there are only two levels of structure. As long as you find it once, you will find the boss. Even if you can't do it completely, you'd better get as close as possible. In this way, the path compression algorithm is generated. Imagine such a scene: two heroes who don't know each other meet and want to know if they can be beaten. So he quickly called his superior and asked, "are you in charge?" The superior said, "I am not. Who is my superior? ask him." Asking all the way, it turned out that the final boss of both of them was father-in-law Cao of the East Factory. "Oh, it turns out that it is the one who remembers himself, Xi Li, who is in the next three battalions and six groups of white-faced gourd babies!" "Nice to meet you. Eighteen groups of fairies and dog tails in the next nine battalions!" The two happily went to drink hand in hand. "wait, wait, wait. I stopped them both. "Oh, by the way, we have to do path compression." The two woke up. The white-faced cucurbit called his superior six group leader: "team leader, I have checked that the master of his study is Grandpa Cao." why don't we work together and worship under Grandpa Cao to save us from being too low-level and look for the mahjong ring in the future. " "well, that makes sense." The white-faced cucurbit then called the third battalion commander who had just visited. The fairy dogtail flower did the same thing. In this way, all the people involved in the query are gathered under the direct leadership of Father Cao. Each query has been optimized, so the number of layers of the whole gate tree will be maintained at a relatively low level. The code of path compression can be understood very well. It doesn't matter if you don't understand it, just copy it and use it. In short, this is the meaning of the function it implements.

Http://i3.6.cn/cvbnm/60/98/92/745b3eac68181e4ee1fa8d1b8bca38bc.jpg

Hdu1232

1 # include 2 using namespace std; 3 int pre [1050]; 4 bool t [1050]; / / t is used to mark the root node of independent blocks 5 int Find (int x) 6 {7 int rystx; 8 while (rhombohedral pre [r]) 9 r=pre [r]; 10 11 int isancx dagger 12 while (pre [I]! = r) 13 {14 j=pre [I]; 15 pre [I] = r 16 return fy 17} 18 fy 19} 20 void mix (int x int fx=Find (x), fy=Find (y) 21 {22 int (x), fy=Find (y); 23 if (fxpurify) 24 {25 int main [fy] = fx;26} 27} 28 int main () 29 {30 int 31 while (scanf ("% d% d", & N) & & N) 32 {33 for

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.