For a problem that I am solving, I need to sort in descending order all edges by weight and keep removing edges till the graph becomes disconnected.
I am performing DFS after removing every edge, to check if the graph is disconnected. So, the time complexity of this method is O(NM).
Is there any way in which I can perform the above task faster?
Sort the edges in ascending order, then start adding edges to your graph until it becomes connected. You can use dsu for it. The total running time will be O(MlogM + Mα(N)).
Edit. This solution may be wrong, I think I'm missing something important and came too fast to a conclusion.
The graph won't always be a tree after removing the edges. For example consider a graph where the edge with the largest cost is a bridge.
Yeah, you're right, I realized it after writing my post. I should think more carefully before writing something.
it's correct you give up too easily
Then it wouldn't get connected until we add the edge with the largest cost i think you didnt understand his solution
I think you didn't understand the problem. when we remove this edge the graph will be disconnected and we we'll stop removing edges.
And in yosei-san's solution we add edges until the graph is connected that means we add edges until we are gonna add the last edge which makes the graph connected
My bad, you're right. I misunderstood his solution I thought he's trying to get the MST of the graph.
Damn, I'm too unsure of myself. Here's a somewhat "legit" proof of why this procedure is correct.
Consider the procedure of removing edges with highest cost, until our graph is decomposed into 2 distinct connected components. After doing this we are left with a set of edges that determine our resulting graph that is not connected, call this set S with k elements that contains the first k edges by increasing weight.
Now consider building the graph from the bottom, using the edges in ascending order. Because the edges are sorted by increasing weight, our procedure will first consider all the edges from S and our graph will remain disconnected while we do this, then when we will consider the first edge that is not in S it will become connected as a consequence of the first procedure.
I think I know the basic operations of DSU, but I am unable to understand how can I find out when does the graph become connected. I'll have to check if the parents of all nodes become common right? So I'll have to check parents of all the N nodes after adding each edge. Wouldn't that take O(Mlog(M).N) ? Please tell me where I am wrong in understanding.
In short, how exactly are we supposed to check whether the graph has become connected or not?
Keep a counter that tells you how many connected components there are in the graph (it's initially N). So, when you do a "union_set" operation, if you are joining two different components you just decrement this counter by one. If the counter becomes 1 that means all nodes are in the same component and therefore the graph is connected.
Thanks
Binary search?
Think more before saying. There is a much simple+effective solution. This solution is also mentioned in one of above comments.
I was just suggesting an alternate solution -- after all, both solutions have
complexity. Some people might find binary search more intuitive.
How do we apply binary search to remove a set of edges, in your method? Can you be more specific on how binary search is supposed to be applied here?
Do a binary search over the number of edges that we need to remove. Let's say that the current candidate is k. Build a graph with all edges except of the last k and check if the graph is connected or not.
pls dont violate the rules of a running contest
http://www.codechef.com/APRIL15/problems/DIVLAND
This blog post is not intended to be related to that problem. The problem I mentioned is a sub-problem in one of my college assignments. If it does violate the rules of that contest, I don't mind removing the blog post :)