884C Bertown Subway

Difficulty : 4/10

I couln't solve this problem during the contest.

but It is not a difficult probelm.

this problem can be solved in various way. I solved it with "union find algorithm". because union find is good algorithms to express "disjoint set".

but the problem has a constraint. It is a "all station has just two degree, Just in and out".

so it can be solved with just loop using parent, visit array.

these two problem solving has different time complexity each other. second one is faster and use less memory. but when express disjoint set, union find is common one.

union find

Source:

https://github.com/ingyeoking13/algorithm/blob/master/cf/dfs/884C.c

loop

Source:

https://github.com/ingyeoking13/algorithm/blob/master/cf/dfs/v2_884C.c