Frequencies for the towers
The radio towers of a network have to be tuned to frequencies. Some pairs of towers interfere with each other, and those must work on different frequencies. Frequencies are few, and the engineers know one useful property of the network: in any part of it there is a tower that interferes with at most d others within that part. A part here is any set of towers, the whole network and any piece of it.
Assign the towers frequencies numbered from 1 to d + 1 so that towers interfering with each other work on different frequencies. If there are several suitable assignments, any will do. In one of the tests the towers are replaced by the blocks of central Almaty from the article on graph colouring: neighbouring blocks must get different colours.
Input
The first line holds the number of towers n, the number of interfering pairs m and the number d (1 ≤ n ≤ 105, 0 ≤ m ≤ 3·105, 0 ≤ d < n). Then come m lines a b: towers a and b interfere with each other (1 ≤ a, b ≤ n, a ≠ b, pairs do not repeat). The property from the statement is guaranteed to hold.
Output
n numbers separated by spaces: the frequencies of towers 1, 2, …, n, each from 1 to d + 1.
Examples
Example 1
4 3 1 1 3 3 4 4 2
1 2 2 1
Example 2
6 10 3 1 2 1 3 1 4 1 5 1 6 2 3 3 4 4 5 5 6 6 2
1 3 2 3 2 4
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 11 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Hand out frequencies greedily in order of the numbers: each tower gets the smallest frequency that its already tuned neighbours do not have. Check it on the first example. Why does the greedy way sometimes use an extra frequency, and what does that depend on?
2Hint 2
A greedy tower gets a frequency no greater than “the number of already tuned neighbours + 1”. So you need an order in which each tower has at most d tuned neighbours by its turn. Which tower is it sensible to tune last, then?
3The idea
Last, the one that has at most d neighbours in the whole network: it exists by the statement, and by its turn at most d frequencies will be taken whatever happens. Remove it from the network. The remaining towers are also a part of the network, and again there is a tower among them with at most d neighbours among the remaining ones: it will be second to last. And so on. This is the smallest-last order from the article: take off the tower with the fewest remaining neighbours, and tune in the reverse order.
4Walkthrough
Why d + 1 frequencies are enough. Take any tower v. When it is tuned, exactly those of its neighbours are tuned that were taken off after v, that is, those still in the network when v was taken off. There are no more of them than v’s remaining neighbours at that moment, and that number is at most d: we take off the tower with the fewest neighbours, and by the statement the remaining part has a tower with at most d of them. So at most d frequencies are taken, and among the numbers 1, …, d + 1 a free one will be found.
Buckets help take the towers off in O(n + m): bucket number k holds the towers that have k neighbours left. When a neighbour is taken off, the tower moves to the bucket one lower, while the old entry stays and is skipped when taken out. The pointer to the lowest non-empty bucket drops by at most one after each removal, so in all it moves O(n + m) steps.
4+Solution
5Complexity
O(n + m): each tower is taken off once, each pair is looked at twice when taking off and twice when tuning. A heap in O((n + m) log n) also works; that is how the article’s listing does it, and it too fits in time.
6Common mistakes
- Greedy in order of the numbers. This is
wrong.py. In the first example towers 1 and 2 get frequency 1, tower 3 frequency 2, and tower 4, a neighbour of both 2 and 3, is left with the third, although two are enough. In the fourth test, a tree built against this order, the greedy way uses 17 frequencies instead of two. - Towers with the most neighbours first. The Welsh–Powell order is often good but gives no guarantee: in the fifth test it needs 6 frequencies with d = 3.
- DSatur. The most constrained next is a strong method, and it passes almost all the tests. But in the eleventh test it needs 4 frequencies with d = 2: the d + 1 guarantee comes from the smallest-last order specifically.
- Taking off by the original number of neighbours. If the towers are sorted by number of neighbours once at the start and it is not updated, you get the same Welsh–Powell order written backwards, and the bound does not work: what matters is the number of neighbours among the remaining ones.