# Homework 10

Due Friday, February 281 at 5:00 PM. Please refer to the homework policy here.

## Problems

1. Let $G = (V,E)$ be an undirected graph with $m$ edges and $n$ vertices, and let $s,t,u \in V$ be three distinct vertices. Design and analyze an algorithm that computes a path from $s$ to $t$ that goes through $u$.
2. A cycle cover of a directed graph is a collection of vertex-disjoint cycles that covers all the vertices. Describe and analyze an efficient algorithm to find a cycle cover for a given graph, or correctly report that no cycle cover exists. 2

1 Because I was late
2 Hint: bipartite matching