# Detect cycle in undirected graph

Below is my code to detect cycle in an undirected graph. Could anyone please review and let me know if I have taken care of all the cases?

The basic idea is to use DFS (non-recursive using stack) and check if already visited vertices are found in the stack.

bool dfsDetectCycle(int vertex, int visited) {
stack<int> s;

s.push(vertex);

while (!s.empty()) {
int np_vertex = s.top();
s.pop();
// visit while poping and check visited
if (visited[np_vertex]) {
// if already visited means there is a cycle
return true;
}
visited[np_vertex] = 1;
cout << np_vertex << "\t";

for (int j = 0; j < v; ++j)
// below !visited[j] is needed to exclude previously visited vertices as well as to exclude parent node of currently in progress vertex
s.push(j);
}
}
else {
for (; it != adjList[np_vertex].end(); ++it)
if (!visited[*it])
s.push(*it);
}
}
return false;
}

bool hasCycle() {
if (empty())
return false;
int visited = {0};
for (int i = 0; i < v; ++i) {
if (!visited[i]) {
if (dfsDetectCycle(i, visited))
return true;
}
}
return false;
}

• Could you maybe make your code example fully self-contained? For instance, I wonder what the data structure representing a graph looks like.
– Juho
Apr 13, 2016 at 16:16
{"ft_lang_label":"__label__en","ft_lang_prob":0.70296204,"math_prob":0.712644,"size":1214,"snap":"2022-27-2022-33","text_gpt3_token_len":331,"char_repetition_ratio":0.14380166,"word_repetition_ratio":0.01010101,"special_character_ratio":0.32289952,"punctuation_ratio":0.18067227,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9536229,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-08-13T22:09:37Z\",\"WARC-Record-ID\":\"<urn:uuid:74a11b39-8be0-493b-a665-fe51d54ba65c>\",\"Content-Length\":\"224423\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:d07032ef-7450-4095-8578-dbd95891baf2>\",\"WARC-Concurrent-To\":\"<urn:uuid:f00b0f9d-caaf-46d9-a15d-da8bbcbc2623>\",\"WARC-IP-Address\":\"151.101.1.69\",\"WARC-Target-URI\":\"https://codereview.stackexchange.com/questions/125512/detect-cycle-in-undirected-graph\",\"WARC-Payload-Digest\":\"sha1:VR5QMYQHEJF366CHNBKAGMVIJKJERKN4\",\"WARC-Block-Digest\":\"sha1:6AO6TZELGXTOMQQJTW6IBDOZM4AEXOIK\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-33/CC-MAIN-2022-33_segments_1659882571987.60_warc_CC-MAIN-20220813202507-20220813232507-00154.warc.gz\"}"}