Cycle Detection Doubt

→ Pay attention

Before contest
Codeforces Round 1002 (Div. 2)
2 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	jiangly	3898
2	tourist	3840
3	orzdevinwang	3706
4	ksun48	3691
5	jqdai0815	3682
6	ecnerwala	3525
7	gamegame	3477
8	Benq	3468
9	Ormlis	3381
10	maroonrk	3379

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	168
2	-is-this-fft-	165
3	Dominater069	161
4	Um_nik	160
5	atcoder_official	159
6	djm03178	157
7	adamant	153
8	luogu_official	150
9	awoo	149
10	TheScrasse	146

View all →

→ Find user

→ Recent actions

Detailed →

aman_naughty's blog

Cycle Detection Doubt

By aman_naughty, history, 6 years ago, In English

Is this code to detect cycle in an undirected graph correct. I have run it on a few test cases and it seems good . Can someone from the community verify it.

code:

code

// p is parent

// s is source

// adj is adjacency list representation of graph

// path is to store cycle and is a set

// ch is children/neighbor of s;

bool dfs(ll s,ll p)

{

visited[s]=true;

for(auto ch:adj[s])

{

    if(ch!=p&&visited[ch])

    {

        path.insert(ch);

        return true;

    }

    if(!visited[ch])

    {

        if(dfs(ch,s))

        {

            path.insert(ch);

            return true;

        }

    }

}

return false;

}

#graph, #cycle, #dfs, #doubt

aman_naughty
6 years ago
3

Comments (2)

Show archived | Write comment?

aman_naughty

6 years ago, # |

-8

why down-voting

→ Reply

M3hran

6 years ago, # ^ |

Because your question is not precise. It's not a good way to ask the community to verify code for you, instead, it may be better to explain your approach in a few sentences or ask for some resources in this topic (of course after searching and not finding anything useful).

→ Reply