--- categories: Graph theory --- A **pseudoforest** is an [undirected graph](Undirected graph) in which every [connected component](Connected component) has at most one [cycle](Cycle (graph theory)). > **Intuition**: If a connected undirected graph on $n$ vertices has $n-1$ edges, then it is a [tree](Tree). If a connected undirected graph on $n$ vertices has $n$ edges, then it has exactly one cycle (i.e. an underlying tree, with an additional edge which closes the cycle). Hence, a pseudoforest consists of connected components, where each component on $k$ vertices consists of either $k-1$ or $k$ edges. ## Directed pseudoforests The concept of a pseudoforest can also be extended to include [directed graphs](Directed graph). A **directed pseudoforest** is a directed graph in which each vertex has at most one outgoing edge; that is, it has [outdegree](Vertex degree) at most one. In the special case where each vertex has outdegree exactly one, the graph is called a [functional graph](Functional graph). ## Problems - [Room Assignments](https://open.kattis.com/problems/roomassignments) [^3] - [Tug of War](https://boi.cses.fi/files/boi2015_day2.pdf) [^1] [^2] ## See also - [Functional graph]() ## External links - [Pseudoforest](https://en.wikipedia.org/wiki/Pseudoforest) [^1]: [^2]: [^3]: