Final answer:
To determine if a directed acyclic graph (DAG) is nice, perform a topological sort and verify that for each vertex, there is a directed path to every vertex that comes after it in the sorted list. If all vertex pairs satisfy this property, the graph is nice; otherwise, it is not.
Step-by-step explanation:
To determine if a given directed acyclic graph G = (V,E) is nice, one effective approach is to use topological sorting. Because the graph is acyclic, a topological order exists for its vertices. A graph G is nice if for every pair of vertices u and v, there is a directed path from u to v or from v to u. Now, if we obtain a topological ordering of the vertices, G is nice if and only if for every vertex u that appears before vertex v in the topological order, there is an edge from u to v, either directly or through a set of edges. If this condition is not met, the graph is not nice.
Here is a step-by-step algorithmic approach:
- Perform a topological sort on the graph. The time complexity for this step on a DAG is O(|V|+|E|).
- Iterate through the sorted list of vertices. For each vertex u, verify that there is a direct or indirect path to every vertex v that comes after u in the topological order.
- If you find a pair of vertices u, v, where there is no path from u to v or v to u, then return false, because the graph is not nice.
- If all pairs satisfy the above condition, then the graph is nice and you can return true.
If at any point a violation of the niceness property is found, the algorithm can terminate early, ensuring efficiency.