Disjoint set system


Plus
Pin


Problem description Progress
ID 31883. Apples
Темы: Disjoint set system   

Dasha has n friends, each has ai apples. All friends form non-overlapping companies. At any time, two companies can merge. Dasha carefully remembered all the actions of her friends. Now she is interested to know how many apples were in each newly formed company. Initially, all friends hang out separately, i.e. there is no company where there is more than one person. Dasha does not have apples and she does not take part in associations.

Input:
The first line contains integers n and k ( 2 <= n <= 300000, 0 <= k <= n - 1 ) - the number of Dasha's friends and the number of events. The second line contains n numbers - ai (0 <= ai <= 10^9) - the number of apples Dasha's i-th friend has. The next k lines contain two numbers u, v ( 1 <= u, v <= n). The event (u, v) means that the company with Dasha's u-th friend has joined the company with the v-th friend. 

Output:
For each of k queries print the number of apples in the new company.

Enter Output
3 2
1 2 3
1 2
1 3
3
6
2 1
999999999 0
1 2
999999999

(c) Ibrahim Ahmad, 2018

ID 32985. Islands
Темы: Disjoint set system   

One state scattered on the islands of Oceania decided to create a network of roads (or rather, bridges). Each bridge can be navigated in both directions. A sequencing plan for the construction of bridges has been developed and it is known that after the construction of all the bridges it will be possible to drive over them from each island to each (perhaps through some intermediate islands
 
However, this moment may come before all the bridges are built. You need to determine such a minimum number of bridges, after the construction of which (in the order determined by the plan), it will be possible to get from any island to any other.
 
Input
The first line contains two numbers: the number of islands N (1≤N≤10000) and the number of bridges in the plan M (1≤M≤50000). Then there are M lines, each containing two numbers x and y (1≤x,y≤N) - the numbers of the cities that are connected by the next bridge in the plan.
 
Output
The program should output a single number - the minimum number of bridges built, after which it will be possible to get from any island to any other.
 
Input Output
4 5
1 2
1 3
2 3
3 4
4 1
4

 

ID 32987. spanning tree
Темы: Disjoint set system   

It is required to find a spanning tree of minimum weight in a connected graph.
 
Input
The first line of the input file contains two natural numbers n and m - the number of vertices and edges of the graph, respectively (1≤n≤20000, 0≤m≤100000). The next m lines contain the description of the edges, one per line. The edge number i is described by three natural numbers bi, ei and wi - the numbers of the ends of the edge and its weight, respectively (1≤bi,ei≤n, 0≤wi≤100000).
 
The graph is connected.
 
Output
Print a single integer - the weight of the minimum spanning tree.
 
Input Output
4 4
1 2 1
2 3 2
3 4 5
4 1 4
7

ID 32986. Component weight
Темы: Disjoint set system   

Edges are added to an undirected weighted graph. Write a program that at some point finds the sum of the weights of edges in a connected component.
 
Input
The first line contains two numbers n and m (1 <= n, m <= 106) - the number of vertices in the column and the number of additions and requests made. This is followed by m lines describing the addition or request. Each line consists of two or four numbers. The first of the numbers indicates the operation code. If the first number is 1, then it is followed by three more numbers x, y, w. This means that an edge is added to the graph from vertex x to vertex y of weight w. (1 <= x < y <= n, 1 <= w <= 103). Multiple edges are allowed. If the first number is 2, then exactly one number x follows it. This means that it is necessary to answer the question, what is the sum of edges in the connected component to which the vertex x (1 <= x <= n) belongs.
 
Output
For each operation with code 2 print the answer to the given problem. Print the answer to each request on a separate line.

 
Examples
# Input Output
1
6 10
2 1
1 1 2 1
2 1
1 2 4 2
2 1
1 1 4 3
2 1
1 3 5 3
2 5
2 6
0
1
3
6
3
0

ID 31929. Ribs
Темы: Disjoint set system   

There are n vertices in an undirected graph, but it has no edges. m edges are gradually added to the graph. 
After each addition of an edge, you need to find out the number of connected components.
A graph can have loops and multiple edges.

Input:
The first line contains two numbers  - n and m (1 <= n <= 300000, 0  <= m <= 500000) - the number of graph vertices and the number of added edges. 
The next m lines contain two numbers u, v (1 <= u, v <= n) - they mean that an edge (u, v) has been added to the graph.
Output:
After each addition of an edge, print the number of connected components of the graph.

Enter Output
3 2
1 2
2 3
2
1
36
1 1
2 2
3 3
1 1
2 2
1 2
3
3
3
3
3
2

(c) Ibrahim Ahmad, 2018

ID 33481. Asya and kittens
Темы: Disjoint set system   

Asya loves animals very much. She recently purchased n kittens, gave them numeric identifiers from 1 to n, and placed them in an enclosure. The aviary is a row of n cells, also numbered from 1 to n. Neighboring cells are separated by mesh partitions, in total there are n & minus; 1 partitions in the enclosure. Initially, exactly one kitten with some number settled in each cell.

Watching the kittens, Asya noticed that they are very friendly and some pairs of kittens living in neighboring cells really want to play with each other. In order not to deprive them of this pleasure, Asya began to remove the partitions between adjacent cells, making them larger.

On the i-th day, Asya did the following.

I noticed that some kittens xi and yi, living in neighboring cells on the i-th day, want to play.
I removed the partition between these cells, turning them into one, in which all the kittens from the two previous cells ended up.
Since Asya did not return the partitions, after n & minus; 1 day the enclosure became a single cell in which all the kittens lived. Being very pedantic, Asya wrote down the kitten IDs xi  and yi  for each of n−1 days in a special journal.

You got a magazine with this information, but you do not know how the kittens were settled in the cells in the first place. Find any distribution of kittens in n original cells that does not contradict the data in the log.

Input
The first line contains an integer n (\(2 \leq n \leq 150000\)) — number of kittens.

The next n−1 lines contain pairs of integers xi , yi  ( \(1 \leq x_i , y_i, \leq n,x_i \neq y_i\) ) — identifiers of kittens, between the cells of which the partition was removed on day i. It is guaranteed that kittens xi  and yi  are not in the same cell as a result of previous cell merging.

Imprint
Print n distinct integers pi (\(1 \leq p_i \leq n\)), where pi — the identifier of the kitten that originally lived in cell number i. If there are several possible answers, print any of them.

Note
In the answer, for example, one of the possible initial settlements of kittens is given, there are other answers. The image below shows how cells were merged for this initial placement of kittens. Please note that with this arrangement, the kittens that became friends on each day according to Asya's journal are in adjacent cells.

 

Input Output
5
14
25
3 1
4 5
3 1 4 2 5

ID 21748. Minimum spanning tree with given edge
Темы: Disjoint set system   

It is required to find in a connected graph a spanning tree of minimum weight that contains a given edge.
 
Input file format:
 
The first line of the input file contains two natural numbers N, M - the number of vertices and edges of the graph, respectively. The next m lines contain the description of the edges, one per line. The edge number i is described by three natural numbers Bi, Ei, Wi, the numbers of the ends of the edge and its weight, respectively (1 <= Bi, Ei <= N, 0 <= Wi <= 2^32-1. N <= 10, M <= 10). The last line introduces the given edge B, E, W.
 
Output file format:
 
The only line of the output file should contain one natural number - the weight of the minimum spanning tree with the given edge. 
 
Input:
 
4 4
1 2 1
2 3 2
3 4 5
4 1 4
1 4 7
 
Output:
10

ID 38132. Portals
Темы: Disjoint set system    Tree Data Structures    Minimum frame   

Besi is located on a network of N (2≤N≤105) vertices labeled 1…N and 2N portals labeled 1…2N. Each portal connects two different vertices u and v (u≠v). A set of portals can connect some pair of vertices.
Each vertex v is adjacent to four different portals. The list of portals of v is given by pv=[pv,1,pv,2,pv,3,pv ,4].

Your current position can be represented by an ordered pair (current vertex,current portal); that is, a pair (v,pv,i) where 1≤v≤N and 1≤i≤4. You can use one of the following operations to change your current position:

Change the current vertex by moving through the current portal.
Switch current portal. At each vertex, the first two portals in the list are paired and the last two portals in the list are also paired. So if your current state is (v,pv,2), then you can switch to use the portal (v,pv,1) and back. Similarly, if your current position is (v,pv,3) you can switch to the portal (v,pv,4) and back. no other switching is allowed (eg you cannot switch from portal pv,2 to portal) pv,4).
There are 4N different states in total. Unfortunately, it may not be that any state is reachable from any state by a sequence of given operations. Therefore, for the cost of cv (1≤cv≤1000) moons, you can rearrange the list of portals adjacent to v, in any order you wish. After that, the first two portals in the list are combined into one pair, and the last two portals into another pair.

For example, if you rearrange the portals of v in the order [pv,3,pv,1,pv,2,pv,4], This means. what if you are at top v,

If you are in the pv,1 portal, you can switch to the pv,3 portal and back
If you are in the pv,2 portal, you can switch to the pv,4 portal and back
Now you cannot switch from portal pv,1 to pv,2, or from portal pv,3 to portal pv,4 and vice versa.
Calculate the minimum number of moons required to modify the network in such a way as to make each state reachable from each state. It is guaranteed that the test data is constructed in such a way that there is at least one way to modify the network in this way.

Input: 
The first line contains N.
Each of the next N lines describes a vertex. The string v+1 contains 5 space-separated integers cv,pv,1,pv,2,pv ,3,pv,4.
It is guaranteed that for each v all pv,1,pv,2,pv,3,pv,4 are distinct, and each portal appears in the lists of exactly two vertices.

Output: 
One line contains the minimum number of moons required to modify the network to make each state reachable from another state.
 

Examples
# Input Output Explanation
1 5
10 1 4 8 9
11 1 2 5 6
12 9 10 2 3
3 4 3 6 7
15 10 8 7 5 
13 It is enough to swap lists of vertices 1 and 4. This requires c1+c4=13 muns. The permutations are: p1=[1,9,4,8] and p4=[7,4,6,3].

ID 38303. Gourmet's Choice
Темы: Dynamic Graph Programming    Depth walk    Disjoint set system   

Error