Weekly Training Solutions: Graph Basics

Problem A (by @LER0ever)

This problem ask you whether it is possible to generate the MST by moving some edges away. If so, print the number of redundant edges, if not print forest.
A modified Kruskal Algorithm: We implement a find_root function that recursively trace back to the root of a node, and if two edges share the same root, we push that into our answer array.
And the size of our answer is the final result.

Problem B (by @LER0ever)

This problem is equivalent to finding a shortest path between in a similarly constructed graph with a starting point and a target. So a simple Dijkstra algorithm can solve this problem.

Problem C (by @RobeZH)

The problem is about checking reachability from a character to another. Since the constraints are small, simply doing dfs each time for a character will do the job.

Bonus Question: What if the alphabet size is some $n \leq 500$ and the length of each of the $m$ ($m \leq 50$) is some $len \leq 2000$?

Problem D (by @Zeyuan He)

To be Presented by Zeyuan.

Problem E (by @RobeZH)

The naive way is to each time delete a different edge and see if the graph is acyclic, which will cost $O(m(m+n))$ time.

A key observation is that by finding a specfic cycle, to make the graph acyclic, we must delete an edge that is on that cycle. Since the number of edges on a cycle is at most $n \leq 500$, then the overall complexity will be improved to be $O(n(m+n))$.

Problem F (by @Lteins)

To be Presented by Leo Liu.