Hi, I’m working on this problem and I don’t understand why cycles within larger connected components don’t increase the answer by 1. For example, if we have s = ABCD and t = BCDC, then the directed graph would have edges A->B, B->C, D->C, C->D. If you change B into D (to break the cycle), s would become ADCD. I think the shortest option after that would be to change ADCD->ADZD->ACZC->BCZC->BCDC, which would take one more than the number of edges, even though the entire graph is a large connected component with a cycle within it. Is there another way to change s into t that is shorter?
Thank you!
You can try writing a brute-force solution if you want to figure it out yourself.
How does the step you remove the loop between C and D change the answer?