UVa 11902

From Algorithmist
Jump to navigation Jump to search

UVa 11902 - Dominator[edit]

Summary[edit]

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[edit]

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[edit]

  • 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.

Implementations[edit]

Exercise left to the reader.

Optimizations[edit]

  • 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[edit]

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[edit]

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|
+---------------------+

Solution[edit]

C++: http://codealltheproblems.blogspot.com/2015/04/uva-11902-dominator.html


References[edit]

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