UVa 10766

From Algorithmist
Jump to: navigation, search

10766 - Organising the Organisation[edit]

Summary[edit]

A company has n departments, which needs to be organized in a hierachy (techically, a tree). Some pairs of the departments confict with each other, and they cannot be made adjacent in the hierarchy. How many hierarchies are possible?

Explanation[edit]

Construct a graph with n vertices. Add edges between all pairs of vertices, which represent non-conflicting departments.

Now, every possible hierarchy represents a spanning tree of this graph. You can use Matrix tree theorem to count them.

Input[edit]

5 5 2
3 1
3 4
4 5
1 4
5 3
4 1 1
1 4
3 0 2

Output[edit]

3
8
3