3
$\begingroup$

I have a problem that states the following :

Given a cyclic graph , output for each node if the node removes all cycles in the graph.

The most trivial way to do this is using a Union-find disjoint set , and for each node , try not putting it in the Union-find disjoint set , if there are no cycles , then this node should output "Yes" , otherwise "No".

This approach would take about $\Theta(N^2)$ time and $\Theta(N)$ memory.

The problem also stated that $N \leq 1,000,000$ which would definitely get a TLE (Time Limit Exceeded) Answer on any problem.

So, my question is, What's the algorithm that would take $\Theta(N \lg N) $ or $\Theta(N)$ time and $\Theta(N)$ memory?

$\endgroup$
4
$\begingroup$

First use Tarjan algorithm to find all of the bridges in the graph. Then remove all of them. Remaining graph should be made of some cycles, such that all of them have at least one common vertex, otherwise we can return false for all vertices. Is possible to check this with DFS, further reasoning is easy, total running time is $O(|V|+|E|)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ do you mean that every edge that is not a bridge is participating in a cycle , so i remove all bridges, after that there should be one connected component bigger than 1 , if there is a solution , otherwise there is no solution , but how do I check for the common vertex between all cycles? $\endgroup$ – mohammed essam Jun 19 '13 at 15:21
  • $\begingroup$ Yes, every edge which is not bridge participating in at least one cycle, this is actually definition of bridge. But I didn't wrote complete answer because I think this is homework or something and you should do it yourself, but for hint: again you know that either you have exactly one cycle or more than one, in the second case, you know that there exists at least one vertex with degree bigger than 2. $\endgroup$ – user742 Jun 19 '13 at 15:28
  • $\begingroup$ It's not a homework , actually I'm just self training for IOI, and I need this algorithm to know how to solve this kind of problem $\endgroup$ – mohammed essam Jun 19 '13 at 15:32
  • $\begingroup$ I can't figure out the right method to find the common node, Can you tell me? $\endgroup$ – mohammed essam Jun 20 '13 at 11:43
  • $\begingroup$ @mohammedessam, I think the hard part is tarjan algorithm, and we cannot expect to someone think about it without knowing that algorithm, but for the rest let think together, if the resulted graph ($G'$) is cycle then is clear, otherwise there should be a node of degree at least three, you can contract all vertices of degree two in $G'$ to make $G"$, then the $G"$ is either made of at most three vertex or more (with possibly parallel edges), in the second case we can return false (for all vertices except for some special vertices, for example if connected to all others)(why?). $\endgroup$ – user742 Jun 20 '13 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.