Make a Forest (Problem D, 2017 ICPC Asia Jakarta Regional Contest, 2017)
Time limit: 1 sec
Memory limit: 256MB
Author: Winardi Kurniawan

# Problem Statement

In 1736, Leonhard Euler wrote a paper on the Seven Bridges of Königsberg which is regarded as the first paper in the history of graph theory. Nowadays, the study of graph theory is considered very important as indicated by the fact that most textbooks in discrete mathematics have a chapter on graph theory.

This problem is related to graph theory, especially on tree and forest. Given $N$ tuples $(u_i, v_i, w_i)$, your task is to construct a forest with a minimum number of trees which satisfies the following seven requirements:

1. Each tree in the forest is a rooted tree;
2. Each node $x$ in the forest has a value $x.A$;
3. Each edge $(x, y)$ in the forest has a value $(x, y).B$;
4. Each tuple $(u_i, v_i, w_i)$ appears exactly once in the forest as two nodes with a parent-child relationship (parent node $p$ and child node $c$) where: $u_i = p.A$, $v_i = c.A$, and $w_i = (p, c).B$;
5. For any non-root and non-leaf node $x$ in the forest, $(p, x).B$ is smaller than any $(x, c).B$, where $p$ is $x$'s parent and $c$ is $x$'s child;
6. All nodes in the forest have at most $M$ children.
7. The forest should contain exactly $N$ edges.

To simplify the problem, it is guaranteed that $w_i$ in any tuple is unique, i.e. no two tuples with the same $w_i$.

Output the number of trees in such forest (the forest should have the minimum number of trees).

# Input

The first line contains two integers: $N\ M$ ($1 \le N,\ M \le 100{,}000$) in a line denoting the number of tuples and the maximum number of children for each node in the forest. The next $N$ following lines, each contains three integers: $u_i\ v_i\ w_i$ ($1 \le u_i,\ v_i \le 2{,}000{,}000{,}000$; $1 \le w_i \le N$) in a line denoting the tuple $(u_i, v_i, w_i)$. It is guaranteed that there will be no two tuples with the same $w_i$.

# Output

The output contains an integer denoting the number of trees in a forest with a minimum number of trees which satisfies the given requirements, in a line.

# Sample Input
```
5 2
2 4 3
4 4 5
4 7 1
7 2 4
4 8 2
```
# Output for Sample Input
```
2
```
# Sample Input
```
5 1
2 4 3
4 4 5
4 7 1
7 2 4
4 8 2
# Output for Sample Input
3
```
# Sample Input
```
5 10
1000 3000 3
2000 4000 5
1000 2000 1
3000 2000 4
2000 3000 2
```
# Output for Sample Input
```
1
```
Explanation for the 1st sample case

![IMAGE](icpc-jakarta-2017-domino-1.png)

For the first sample, this forest is the only forest which satisfies all the requirements. There are 2 trees in this forest.

![IMAGE](icpc-jakarta-2017-domino-2.png)

On the other hand, this forest does not satisfy the requirements due to:

1. Node **b** violates requirement #5 as $(a,b).B = 3$ is larger than $(b,c).B = 1$ and $(b,d).B = 2$.
2. Node **b** violates requirement #6 as it has 3 children (note that $M = 2$).
3. There are 6 edges in the forest while $N = 5$ (violates requirement #7).

Note that violating even one requirement already makes the forest invalid.


Sample inputs:
5 2
2 4 3
4 4 5
4 7 1
7 2 4
4 8 2

5 1
2 4 3
4 4 5
4 7 1
7 2 4
4 8 2

5 10
1000 3000 3
2000 4000 5
1000 2000 1
3000 2000 4
2000 3000 2

Sample outputs:
2

3

1

# Solution Analysis
Analysis author: Suhendry Effendy

The problem description makes the problem looks harder than it should be. Once you understand the problem better, you will realise that it actually is a fairly easy problem.

The first three requirements simply denote a forest with rooted trees where each vertex and edge has a label/value (not necessarily unique). Now, let's observe the following four points:

- (a) There are $N$ tuples $(u_i, v_i, w_i)$,
- (b) Each tuple appears exactly once as an edge in the forest,
- (c) No two tuples have the same $w_i$,
- (d) The forest should contain exactly $N$ edges.

These points imply that there is a one-to-one relationship between each tuple and edge in the forest.  
So, processing a tuple is equal to adding an edge (and vertex) in the forest.

Requirement #5 forces us to prioritise tuples with smaller $w_i$ to be closer to the root than tuples with larger $w_i$.  
We can construct the same forest by processing each tuple one by one in increasing order of $w_i$.  
When we process a tuple $(u_i, v_i)$, add a new vertex with label $v_i$ as a child of an existing vertex with label $u_i$ which still has fewer than $M$ children, or create a new vertex with label $u_i$ as a root of a new tree and add vertex with label $v_i$ as its child.

The key observation is: It doesn't matter which vertex with label $u_i$ we choose when we process the tuple $(u_i, v_i)$, as long as the chosen vertex still has fewer than $M$ children; otherwise, a new tree is inevitable (greedy solution).

**Solution**:  
Sort all the tuples $(u_i, v_i, w_i)$ based on $w_i$ in ascending order. Add each tuple in this order into the forest one at a time, i.e. add a new vertex with label $v_i$ as a child of *any* existing vertex with label $u_i$ which still has fewer than $M$ children; if there is no such vertex, then create a new tree with label $u_i$ as its root, and put vertex with label $v_i$ as its child.

Note that when implementing the solution, we don't need to actually build the forest.  
We only need to keep track the number of trees, the number of nodes for each label, and the number of existing children for each label. Alternatively, the last two can be combined into the number of possible new children for each label.

Here is one implementation in C/C++. The time-complexity for this solution is $O(N \log N)$.
```
#include <bits/stdc++.h>
using namespace std;

struct tuple { int u, v, w; };
bool operator < (const tuple &x, const tuple &y) { return x.w < y.w; };

int N, M;
tuple arr[100005];
map <int,int> cap;
int   main()     {
    scanf( "%d %d", &N, &M ); 
    for ( int i = 0; i < N; i++ )
        scanf( "%d %d %d", &arr[i].u, &arr[i].v, &arr[i].w );
    sort(arr,arr+N);
    int ans = 0;
    for ( int i = 0; i < N; i++ ) {
        if ( cap[arr[i].u] == 0 ) {
        cap[arr[i].u] += M - 1;
        cap[arr[i].v] += M;
        ans++;
        }
        else {
            cap[arr[i].u]--;
            cap[arr[i].v] += M;
        }
    }
    printf( "%d\n", ans );
    return 0;
}
```

Special judge (C++ scorer):