# Semi-Connected Directed Graph
# Part a
**Give an example of a directed acyclic graph with a unique source that is not semi-connected**

**Example**
Take vertices s, a, and b
Take edges:
s --> a
s --> b

* This graph is a directed acyclic graph and has a unique source s
* the graph is NOT semi-connected because for the pair (a,b), there is no path from a to b and no path from b to a. This fails the condition stating that for every pair (u,v) there must be a path from u to v and a path from v to u.
# Part b
**Describe and analyze an algorithm to determine whether a given directed acyclic graph is semi-connected**
hint: topological sort the DAG nodes first

**Algorithm**
A semi-connected DAG can be detected using topological ordering.
* topologically sort the vertices
* for each i = 1, 2,..., n - 1, check whether there is a direct edge
* if an edge doesn't exist for some i, return "not semi-connected"
* is every pair has an edge (Vi --> Vi+1), return "semi-connected"

**Analysis + Running Time**
* if there is an edge Vi --> Vi+1 for every consecutive pair in topological order, then there is a path to visit all vertices. This means the graph is semi-connected
* if every consecutive pair has a directed edge, the ordering forms a directed path through all vertices --> semi-connected
* otherwise, if any edge is missing, Vi to Vi+1 OR Vi+1 to Vi is not possible --> NOT semi-connected
* must check edges between consecutive vertices in topological order to determine if it is actually semi-connected

Running time:
* topological sort --> O(V + E)
* for each vertex Vi, check if Vi+1 is in its adjacency list --> O(V + E)

Total time: O(V + E)