Algorithms-on-graphs--Adding-Exits-to-a-Maze

Problem Introduction Now you decide to make sure that there are no dead zones in a maze, that is, that at least one exit is reachable from each cell. For this, you find connected components of the corresponding undirected graph and ensure that each component contains an exit cell. Problem Description Task. Given an undirected graph with 𝑛 vertices and 𝑚 edges, compute the number of connected components in it. Input Format. A graph is given in the standard format. Constraints. 1 ≤ 𝑛 ≤ 103, 0 ≤ 𝑚 ≤ 103. Output Format. Output the number of connected components.

Determining-an-Order-of-Courses

Problem Introduction Now, when you are sure that there are no cyclic dependencies in the given CS curriculum, you would like to find an order of all courses that is consistent with all dependencies. For this, you find a topological ordering of the corresponding directed graph. Problem Description Task. Compute a topological ordering of a given directed acyclic graph (DAG) with 𝑛 vertices and 𝑚 edges. Input Format. A graph is given in the standard format. Constraints. 1 ≤ 𝑛 ≤ 105, 0 ≤ 𝑚 ≤ 105. The given graph is guaranteed to be acyclic. Output Format. Output any topological ordering of its vertices. (Many DAGs have more than just one topological ordering. You may output any of them.)