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

This article introduces what the learning experience of STL and search application is, the content is very detailed, interested friends can refer to it, hope to be helpful to you.

Let's first introduce the topic shared today.

Brief description of the topic: there are n individuals, among which there are many pairs of friends (it does not rule out that some people have no friends). This kind of friend relationship satisfies the symmetrical and transitive nature (whether the reflexive relationship has no effect on this problem), that is, if An and B are friends, then B and An are friends; if An and B are friends and B and C are friends, An and C are also friends. In short: people who are satisfied with a friend relationship either have a direct friend relationship, or two people have a mutual friend.

From the above characteristics, many relationship networks can be established among a group.

Analyze the characteristics of the established friend network. The symmetry shows that the relationship is undirected, and the network also satisfies transitivity, for example, if there are four people 1, 2, 3 and 4 in one of the relationship networks.

Known

one

two

two

three

one

four

Then

By 1

2 and 2

3 can lead to 1.

three

By 1

2 and 1

4 can get 2.

four

By 2

3 and 2

4 can lead to 3.

four

Summary:

The friends with number 1 are: 2, 3, 4

The friends with number 2 are: 1, 3, 4

The friends with number 3 are: 1, 2, 4

The friends with number 4 are: 1, 2, 3

It can be concluded that any two people in this network must be friends, and once a person can have sex with someone on the network, that person also has a relationship with everyone else. If a person has friends, then these people who are friends with each other must be able to form a closed network of relationships, which forms two extremes: either they are alone and have no friends, or they must become friends with everyone in their network. Explain with the knowledge of graph theory: according to the symmetry of friend relations, it can be concluded that the graph formed in this topic is an undirected graph, and the formed relation network is either a trivial graph (with only one isolated point) or a complete graph (any two points are connected).

The requirements of the topic: the first line gives the total number n and the logarithm m of the total relationship, numbers n individuals from 1 to n, and gives the m-pair number that satisfies the friend relationship. Try to judge whether the given m-pair relationship constitutes a network system that satisfies the friend relationship mentioned in the topic. Output YES, otherwise output NO.

The input and output data requirements are as follows:

Neither m nor n exceeds 150000.

The test examples are as follows:

After you have an overview of the topic, you might as well take a look at the test examples.

Take the first group of test samples as an example to analyze:

N = 4, m = 3, three pairs of friends can build the following relationship network system:

From the above picture, we can see that the left half satisfies the complete graph and the right half satisfies the trivial graph. The system satisfies the friend relationship required by the question, so the answer YES is output.

Let's look at the second set of test data:

N = 4, m = 4, from the four pairs of relationships, the following relational network system can be built:

As can be seen from the above figure, 4 is not directly connected to 2 and 1, so it does not meet the complete graph condition. The answer is NO.

After analyzing the above two examples, it is found that to judge whether a relational network system satisfies the conditions, it is only necessary to judge each connected component, and if there is a component that is neither a complete graph nor a trivial graph, then the system does not meet the conditions.

When the human eye looks at it, it may be possible to see at a glance whether a connected component or even a relational network system meets the conditions, but how does the computer judge? When judging by computer, there must be a standard for the formation of a fixed pattern. Comparing this standard with the formed examples, the complete match is correct and the incomplete match is wrong. This process is divided into the following two steps:

The first step: the relationship network system given by the input information should be established and stored. The establishment of a relationship network system is divided into two aspects. the first aspect, because the topic requires to judge whether a given relationship meets the conditions, it is necessary to store the originally given m-pair relationship, and the second aspect, because of the characteristics of the friend relationship itself, it is necessary to reflect the relationship between symmetry and transitivity, that is, in the process of input, the graph needs to be improved. Fill in the relationship between symmetry and transitivity. Therefore, the topic must establish two independent structures, one simply stores the relationship given by the topic, and the other is used to store the modified relational network system.

Step 2: compare the original relationship with the modified relationship.

After the introduction of the theoretical knowledge, the following is the specific implementation plan:

As in the past, introduce two kinds of common ideas and modified ideas.

Option one

Storage of original relationship

The original relationship gives the number of m to friends (no repetition). In order to satisfy the symmetry relationship, we should store the two-way relationship. Recall that the most intuitive structure of the storage graph is the adjacency matrix, which is, to put it bluntly, a two-dimensional array. The advantage of this structure is that the time complexity of finding the relationship between any two elements is o (1), but the disadvantage of this structure is fatal. When the space utilization is not high and traversing the whole graph, it consumes too much time. The range of m and n of this question is 150000, it is certainly not realistic to open a two-dimensional array (I will not tell you that the program crashes so that even the numbers can not be read when I try); there is also a way to store the graph structure-adjacency table, this structure space utilization is relatively high, however, the implementation of the linked list is more troublesome, a little carelessness, there will be pointer out of bounds error. However, under the premise of being familiar with linked list operation, it is also a feasible scheme.

Storage of modified relationships

The revised relationship should meet the symmetry and transitivity. According to the requirements given by the topic, people who have friends with each other can be put in the same set. Why can you just deposit it in the same collection? Because any relational network in this problem is an undirected complete graph, that is, any individual in each relational network is associated with all the other individuals in the same relational network, and all members do not have the characteristics of special need to be marked. If you only need to divide all members into several collections, it is only appropriate to use and look up sets to achieve this step.

And check the function of the set: divide all the elements into several sets according to a specific relationship, and select a representative element (commonly known as father) in each set to represent the collection, this behavior is similar to dividing several classes in the environment of the school, each class selects a monitor, and the monitor acts as the representative of the class to communicate with the outside world.

A comparison between the original relationship and the modified relationship

Because the modified relationship is a network of relations established according to the correct relationship, it is necessary to judge whether the original relationship is different from the modified relationship, that is, for each pair of relationships that appear in the modified relationship, whether the relationship is stored in the original diagram. According to this idea, every time a pair of relationships are found in the modified relationship network, it is necessary to find out whether the relationship exists in the adjacency matrix (or adjacency table) where the original relationship is stored. The time complexity of this idea is much more than o (naughn), and it is not advisable on the scale of 150000.

The storage structure of the original relationship and the modified relationship is better to improve, but how to improve the relationship in this direction? Since traversal will time out, can you improve it with a different way of thinking? Now let's get back to the idea that a complete graph has many properties. Can we use some of its properties to avoid traversing the whole graph? For a complete graph with n nodes, each node must be connected with the other nodes, which means that the number of relations associated with it is nMul, so it is only necessary to determine the number of nodes in each relational network, and then traverse the original graph to determine whether each node satisfies the above relationship with the relational network.

Now the problem turns into two simple questions:

First, find out the number of connected branches and the corresponding nodes in the relational network system.

Second, solve the number of relations related to each node in the original relational network system and compare it with the corresponding number in the modified relationship.

Prepare all the data you need, which only needs to be traversed once and the time complexity is o (n). This leads to the following plan.

Option 2

Storage of original relationship

The dynamic storage of the original relational network system is realized by using the vector container in STL. The vector array g [1e6] of 1e6 is opened, and all individuals related to the number I are stored in the g [I] component. At this time, call g [I] directly. The number of relations related to I can be calculated by the size () function. (it is important to note that the relationship established here is two-way.)

Storage of modified relationships

For the modified relational network system, the idea of parallel search set can be used to modify the father array. Because in the process of comparing the original relationship with the modified relationship, only the corresponding relationship between the representatives of connected branches and the total number of nodes is used, so the mapping relationship between the two can be stored by using the map container in STL.

Comparison between original and revised drawings

Compare the correlation coefficient g [I] of the components numbered I one by one. Whether the number of nodes in the relational network where I is stored in size () and map map [find (I)] satisfies

Map [find (I)]-1 = g [I]. Size ()

This achieves the purpose of building a graph and avoiding traversing the graph.

What is the learning experience of STL and parallel search application is shared here, I hope that the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

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.