# UVa 10766

Jump to navigation
Jump to search

## 10766 - Organising the Organisation[edit]

## Summary[edit]

A company has 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 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