# UVa 10766

## Summary

A company has ${\displaystyle 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

Construct a graph with ${\displaystyle 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.

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

```3
8
3
```