Scribd
Upload
9 views2 pages

Soru 3

Uploaded by

nur b
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views2 pages

Soru 3

Uploaded by

nur b
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

#include<iostream>

#include<set>
#define NODE 4
using namespace std;

int graph[NODE][NODE] = {
{0, 1, 0, 0},
{1, 0, 1, 1},
{1, 1, 0, 0},
{0, 1, 0, 0},
};

bool dfs(int vertex, set<int>& visited, int parent) {


visited.insert(vertex);
for (int v = 0; v < NODE; v++) {
if (graph[vertex][v]) {
if (v == parent) //if v is the parent not move that direction
continue;
if (visited.find(v) != visited.end()) //if v is already visited
return true;
if (dfs(v, visited, vertex))
return true;
}
}
return false;
}

bool hasCycle() {
set<int> visited; //visited set
for (int v = 0; v < NODE; v++) {
if (visited.find(v) != visited.end()) //when visited holds v, jump to next iteration
continue;
if (dfs(v, visited, -1)) { //-1 as no parent of starting vertex
return true;
}
}
return false;
}

int main() {
bool res;
res = hasCycle();
if (res)
cout << "The graph has cycle." << endl;
else
cout << "The graph has no cycle." << endl;
}

You might also like