1697 Checking Existence of Edge Length Limited Paths

1697. Checking Existence of Edge Length Limited Paths Idea This problem at first looks a lot like a shortest path problem, but the test case size(\(10^5\)) seems to be too big. Another observation is that the problem doesn’t really ask for shortest path, instead it asks if the max weight along the path is smaller than something, (hopefully) this relaxes the problem a little bit. As there is no easy way to find out the max path weight given two random nodes in the graph(probably just DFS and BFS, which result in \(n^2\) time complexity, Floyd-Warshall algorithm has \(n^3\)), we try something else....

April 29, 2023 · mimimi

1101 the Earliest Moment When Everyone Become Friends

Union Find with a counter that does count-- when there is a successful union, when the count reach 1 (everything is connected) return the timestamp Trick: remember to sort by timestamp

March 19, 2023 · mimimi