# Semi-connected Directed Graph
## Problem:
A directed graph G is *semi-connected* if, for every pair of vertices u and v, either u is reachable from v or v is reachable from u (or both).

## a) Give an example of a directed acyclic graph with a unique source that is not semi-connected
Let us use the example:
S = {A,B,C}
Edges: A->B

This is **not** semi-connected since:
- There is no path B->C or from C->B
This means that with these states, there is no instance in which C is connected to the states.

## b) Describe and analyze an algorithm to determine whether a given directed acyclic graph is semi-connected
### Algorithm Description:
This is for my memorization:
- Acyclic: No loops in the graph that could lead to the return of an already visisted node
- Directed: Cannot go both ways from an example A->B and B->A, it has to be one of them OR there needs to be two specifically outlined edges for those.

For our algorithm, we are going to compute any topological ordering of the DAG (directed acyclic graph) since a DAG is semi-connected iff the topological order has the property that for every consecutive pair of verticies, there is a pth from vi to vi+1. Now the topoligical ordering is computed, for each consecutive pair of (vi,vi+1), check if v, can reach vi+1. We will use dfs to compute the reachability. If all pairs satisfy reachability, the graph is semi-connected. If at least one pair does not, then the graph is not semi-connected.

fun isSemiConnected(G) {
    var topo = topologicalsort(G) // Assuming we have a topological sort function already
    
    for (int i=0; i < topo.length -1; i++) {
        var u = topo[i];
        var v = topo[i+1];
        
        if (reachable(G, u, v) == false) {
            return false;
        }
    }
    
    return true;
}

fun reachable(G, s, t) {
    dfs(s) // Assuming we have dfs function already
    
    return (t is visited) // Checking during dfs if t was found
}

### Correctness Proof:
Goal: We want to prove that the algorithm correctly determines whether a DAG G is semi-connected.

### Base Cases:
- 0 Vertices: Since there are no vertices to consider, there is no way for the output to be false, thus true.
- 1 Vertex: Similar to vertices of 0. If there is only 1 vertex, there is no way to output false as you are already visiting this specific vertex, thus true.
- 2 Vertices: The algorithm will check the only pair in topological order and immediately showcases if true or not.

### Inductive Step:
Assume the algorithm works correctly for all DAGs with fewer than n vertices. Consider a DAG G with n vertices and topological order of

#### If the algorithm returnes true, then the graph is semi-connected
The algorithm now checks that for every consecutive pair (vi, vi+1), there is a path from vi to vi+1.
By induction on the positions:
since v1 -> v2 and v2 -> v3, by transivity: v1 -> v2 -> ... -> vn
This works for any arbitray pair vi, vj:
- If i < j, then by chaining consecutive reachability, vi -> vj
- If j < i, the symmetric case applies
Thus, all vertex pairs are comparable by reachability, thus semi-connected.

#### If the graph is semi-connected, the algorithm returns true
If G is semi-connected, then reachability induces a total order on vertices. Every topological order must respect this, so for any consecutive pair (vi, vi+1):
- They must be comparable: vi -> vi+1 or vi+1 -> vi
- But topological order blocks backward edges, so it must be only: vi -> vi+1
Thus, every pair passes the reachability test, so the algorithm will return true.

### Time Complexity
**Topological Sort** T = O(V+E)
This is because you are looking through ALL vertices and ALL edges

**Reachability Check** T = O(V+E)
Same reasoning as Topological sort

Thus, the algorithm recurrence is