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?

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.

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

I can't figure out the right method to find the common node, Can you tell me?

@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?).

In the first case you should reason it out yourself. (how to recover contracted edges). May be there is a simpler and more elegant algorithm, but using Tarjan algorithm and then edge contraction is first thing comes to mind.

I drew some graphs and it seems that the node with the most degree is the candidate, and I should just check for it using the method I stated above (using Union-find disjoint set), Is that right?

No, I don't think so. You know what is the edge contraction? Just in remaining graph run edge contraction to remove vertices of degree two. do not contract if you have a vertex of degree more than 2 in $G'$ (may be in $G"$ is of degree two).

Sorry I have not much time to chat, but think about what I said before, then write down your thought

Hi, so why isn't the method i said wrong?

You mean why is the method you said wrong?

may be you have vertex of degree two which participate in all cycles. You should also return that one.

I guess that there is no vertex of degree two that is participating in all cycles

unless there is only one cycle, and that's a special case

a vertex of degree two means that it is only in one cycle

the vertex of degree two doesn't mean is ini one cycle

But yes you are right, it cannot participate in all cycles

So you can contract them all to skip them

if it is in two cycles , that means that one cycle is inside the other , that means that there a node of degree three that if removed would remove the two cycles, right?

yes

there is a node of degree at least three

(not three)

and I think that contracting them would waste time, I can just loop on the nodes

and skip them

yes contraction is just name, means skip them all

there are two main operation in edges

contraction and deletion

sometimes you will contract them sometimes you will delete them

here we need contraction

ok, thanks I'll try that method and I'll let you know if it works :)

but that method should not work

because if you want to run a query is O(n^2)

why?

I can't see you can do it faster than $n.E$

the reason I mentioned bridge is this, because bridges may cause making high degree vertex

which is useless

no, It's O(N) N for Tarjan and N for counting the degree and another N for counting the connected components

but before you see there is an bridge or not

I meant my method after Tarjan :D

OK

this is OK

I was thinking you want do it naively ;)

Sorry for that

OK, then is it now going to work?

NP :)

Yes, I think so

OK , I'll let you know if it does (or doesn't actually :D )

But I'm 99% sure about the way I wrote in comment, I didn't prove it, but seems ok to me

Sometimes we don't have time for proof ;)

I should think about it, but really I have not much time to right complete proof.

to write right complete proof*

It's OK , though I'm going to IOI this year :D

nice

Egypt team

best lucks

very nice

Thanks :)

Anyway, you should think more, also you should prove everything before implement it. If you get penalty this would be very bad in your final score.

there are no penalties ;)

So is ok.

only number of submissions limit , which is 100

I'll only be wasting time in implementing it

I was competing in ACM, and one time we loosed in west Asian group, just because of very bad penalty (we got 4th place).

but if it was right , I'll be wasting time trying to prove it ;)

No proving improves your thinking ability.

Also helps you to solve and understand other problems.

but on timed contests it could be a waste of time

NO :)

but yes if you allowed 100 submission is OK\

:D

But for practice, never forget proof.

Sometimes some solutions don't need proof , or don't have proof ;)

Then you cannot get better.

ok I have to go

this was my two cents

I said sometimes :)

Thanks :)

bye

:)

bye :)