CP2: Topic 8: Union Find and Minimal Spanning Tree
Competitive Programming II (Spring 2020)
Ninghui Li
Union Find (aka Disjoint-Set)
Data Structure
Union-Find (aka Disjoint-Set) Data Structure
Implementation of Union-Find
Union-Find: Strategy for Unions for Efficiency
Union By Size Example
0
1
2
3
8
7
4
5
6
+
=
0
1
2
3
4
5
8
7
6
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 0 | 0 | 1 | 2 | 2 | 6 | 6 | 6 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
0 | 0 | 0 | 1 | 2 | 2 | 0 | 6 | 6 |
Union(4, 7);
Union-Find: Path Compression
Path Compression Example
0
1
2
3
4
5
8
7
6
9
0
1
2
3
4
5
8
7
6
9
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
0 | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 4 | 5 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
0 | 0 | 0 | 1 | 0 | 2 | 3 | 3 | 0 | 5 |
Find(8);
Union Find Code in Java (Union by size)
class UF {
int[] parent, size; // parent[i] = parent of i
int count; // number of components
public UF(int n) {
count = n; parent = new int[n]; size = new int[n];
for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
}
public int find(int p) {
while (p!=parent[p]) { parent[p]=parent[parent[p]]; p=parent[p]; }
return p;
}
public void union(int p, int q) {
int a = find(p), b = find(q);
if (a == b) return;
if (size[a] <= size[b]) { parent[a]=b; size[b]+= size[a]; }
else { parent[b] = a; size[a]+=size[b]; }
count--;
}
}
Minimal Spanning Tree
Minimum Spanning Tree
4
2
5
7
10
3
6
1
8
9
5
2
4
2
7
3
6
1
5
2
MST
Kruskal’s Algorithm
Prim’s Algorithm
Prim’s Algorithm
Minimal Spanning Tree: Example 1
Kattis: A Feast for Cats
Given M ml of milk, and C cats – each pair of cats being a given distance apart from each other – determine if it’s possible to feed every cat at least 1 ml of milk. You will spill 1 ml of the milk you carry for every meter you walk. Instead of carrying all the milk at once, you may serve a cat more milk than needed and pick it up when backtracking (the cat will not drink the excess milk before you’re finished walking). The fridge (which has milk) is placed at the very same location as cat 0.
A Feast for Cats asks for a Minimal Spanning Tree (MST)
Implementation of Kruskal’s Algorithm for Cats
int[][] edges; // edges[i]:{weight, u, v}
Arrays.sort(edges, 0, E, comp);
UF nodes = new UF(N);
int mst_cost = 0, k = 0;
while (nodes.count > 1) { // graph is fully connected
int u = edges[k][1], v = edges[k][2];
if (nodes.find(u) != nodes.find(v)) {
mst_cost += edges[k][0];
nodes.union(u, v);
}
k++;
}
Minimal Spanning Tree: Example 2
Kattis: Nature Reserve
Kattis: Nature Reserve
Give N stations, where S of them already have a program of L bytes, find out the minimal amount of energy needed to have all stations install the program. There are M links among pairs of stations. Activating a link between stations i and j costs energy E_{ij}. Transmitting one byte costs 1 unit of energy.
1 ≤ S ≤ N ≤ 10^4 1 ≤ M ≤ min(10^6, N(N-1)/2) 1 ≤ L ≤ 10^6
Kattis: Nature Reserve Analysis
Java Code for Nature Reserve
int connected = 0; // number of connected nodes
int[] cs = new int[N]; // current best cost for node
for (int i=0; i<N; i++) cs[i] = LARGE_INT;
long cost = ((long) L) * (N - S); // cost of transmission
while (connected < N) { //
int[] eg = pq.poll(); // pq initialized with S source, with 0
int u = eg[1];
if (cs[u] != 0) { // node already connected has cs[u]==0
cost += eg[0]; cs[u] = 0; connected ++;
for (int[] edg : adj.get(u)) {
int v = edg[1], w = edg[0];
if (cs[v] > w) { pq.add(edg); cs[v] = w; }
}
}
}
Kattis: Association for Control over Minds
There are at most 500001 types of items, and you have one item of each type. You have 2≤N≤200000 recipes for potions, each consisting of some item types. You go through the recipes one by one and use cauldrons to make potions. You can make a potion if you can combine existing potions and unused items to get exactly the same set of items as in the recipe. You will make it when you can, and skip a recipe when you cannot. Computer the number of potions you can make.
Input: 5 2 1 2 2 3 4 2 1 5 5 1 2 3 4 5 2 1 2
Output: 3
Association for Control over Minds: Analysis
Java Code for Mind Control
UF items = new UF(500001);
int N = in.nextInt(), ans = 0;
for (int i=0; i<N; i++) { // loop over all recipes
int M = in.nextInt(), size = 0;
HashSet<Integer> cauld = new HashSet<Integer>();
for (int j=0; j<M; j++) {
int x = in.nextInt(), y = items.find(x);
if (cauld.contains(y)) continue;
cauld.add(y); size += items.size[y];
}
if (size != M) continue;
ans++; int y = -1;
for (int x : cauld) if (y==-1) y = x;
else items.union(x,y);
}
Hints for Homework