# UVa 11902

## Summary

In graph theory, a node X dominates a node Y if every path from the predefined start node to Y must go through X. If Y is not reachable from the start node then node Y does not have any dominator. By definition, every node reachable from the start node dominates itself.

Given a directed graph, find the dominators of every node assuming the zeroth node is the start node.

## Explanation

Use DFS (or BFS) to compute an initially reachable set of nodes starting at node 0. Then, iteratively remove (or ignore) each node and recompute DFS (or BFS) reachability from node 0. If a given node i was reachable before removing another node j, then j dominates i.

## Gotchas

• The graph may be disconnected. There can be two (or more) disjoint subgraphs in the input. In the most extreme case, node 0 can be disconnected. Consider reachability from node 0 only.
• Pay attention to output formatting.

## Optimizations

• It is only necessary to remove each node j to test for domination once. That is, test only O(N) node removals, not O(N2).
• Consider storing the graph using an adjacency list instead of the given matrix form.
• Directly generate the output string for each row instead of using a boolean matrix to print each element. This requires only O(N) printf (or write) calls to create the output instead of O(N2) calls. However, I/O does not dominate this problem (pardon the pun!).

## Input

```5
10
0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 0 0 0
10
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
1 0 0 1 1 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
6
1 0 0 0 0 0
0 0 0 0 0 0
0 1 0 0 1 0
0 0 0 0 0 0
0 1 0 0 0 0
1 0 0 0 0 0
11
0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
```

## Output

```Case 1:
+-------------------+
|Y|Y|N|N|N|N|N|N|N|N|
+-------------------+
|N|Y|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
Case 2:
+---------+
|Y|N|N|N|N|
+---------+
|N|N|N|N|N|
+---------+
|N|N|N|N|N|
+---------+
|N|N|N|N|N|
+---------+
|N|N|N|N|N|
+---------+
Case 3:
+-------------------+
|Y|N|N|N|Y|Y|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|Y|N|N|N|N|N|
+-------------------+
|N|N|N|N|Y|Y|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
|N|N|N|N|N|N|N|N|N|N|
+-------------------+
Case 4:
+-----------+
|Y|N|N|N|N|N|
+-----------+
|N|N|N|N|N|N|
+-----------+
|N|N|N|N|N|N|
+-----------+
|N|N|N|N|N|N|
+-----------+
|N|N|N|N|N|N|
+-----------+
|N|N|N|N|N|N|
+-----------+
Case 5:
+---------------------+
|Y|Y|Y|N|Y|N|Y|N|Y|N|Y|
+---------------------+
|N|Y|N|N|N|N|N|N|N|N|Y|
+---------------------+
|N|N|Y|N|N|N|N|N|N|N|N|
+---------------------+
|N|N|N|N|N|N|N|N|N|N|N|
+---------------------+
|N|Y|Y|N|Y|N|Y|N|Y|N|Y|
+---------------------+
|N|N|N|N|N|N|N|N|N|N|N|
+---------------------+
|N|N|Y|N|N|N|Y|N|Y|N|N|
+---------------------+
|N|N|N|N|N|N|N|N|N|N|N|
+---------------------+
|N|N|Y|N|N|N|N|N|Y|N|N|
+---------------------+
|N|N|N|N|N|N|N|N|N|N|N|
+---------------------+
|N|N|N|N|N|N|N|N|N|N|Y|
+---------------------+
```

## References

1. http://en.wikipedia.org/wiki/Dominator_%28graph_theory%29