#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
struct graph
{
int e,v;
std::vector< vector <int> > vec;
};
void addEdge(graph *&g,int s,int d)
{
g->vec[s].push_back(d);
}
graph *create(int v,int e)
{
graph *g=new graph;
g->v=v;
g->e=e;
g->vec.resize(v);
return g;
}
int dfs(graph *g,int k,int visited[],int recstack[])
{
if(!visited[k]){
recstack[k]=1;
visited[k]=1;
for(int j=0;j<g->vec[k].size();j++)
{
if(!visited[g->vec[k][j]]&&dfs(g,g->vec[k][j],visited,recstack))
{
return 1;
}
else if(recstack[g->vec[k][j]])
return 1;
}
}
recstack[k]=0;
return 0;
}
int main()
{
int visited[100],recstack[100];
graph*g=create(5,7);
addEdge(g, 0, 1);
addEdge(g, 0, 4);
addEdge(g, 1, 2);
addEdge(g, 1, 3);
addEdge(g, 1, 4);
addEdge(g, 2, 0);
addEdge(g, 3, 4);
for(int i=0;i<100;i++)
{
recstack[i]=0;
visited[i]=0;
}
for (int i = 0; i < 5; i++)
{
for(int i1=0;i1<100;i1++)
{
recstack[i1]=0;
visited[i1]=0;
}
if(dfs(g,i,visited,recstack))
{
cout<<" Cycle present ";
break;
}
}
return 0;
}
#include <vector>
#include <stack>
#include <queue>
using namespace std;
struct graph
{
int e,v;
std::vector< vector <int> > vec;
};
void addEdge(graph *&g,int s,int d)
{
g->vec[s].push_back(d);
}
graph *create(int v,int e)
{
graph *g=new graph;
g->v=v;
g->e=e;
g->vec.resize(v);
return g;
}
int dfs(graph *g,int k,int visited[],int recstack[])
{
if(!visited[k]){
recstack[k]=1;
visited[k]=1;
for(int j=0;j<g->vec[k].size();j++)
{
if(!visited[g->vec[k][j]]&&dfs(g,g->vec[k][j],visited,recstack))
{
return 1;
}
else if(recstack[g->vec[k][j]])
return 1;
}
}
recstack[k]=0;
return 0;
}
int main()
{
int visited[100],recstack[100];
graph*g=create(5,7);
addEdge(g, 0, 1);
addEdge(g, 0, 4);
addEdge(g, 1, 2);
addEdge(g, 1, 3);
addEdge(g, 1, 4);
addEdge(g, 2, 0);
addEdge(g, 3, 4);
for(int i=0;i<100;i++)
{
recstack[i]=0;
visited[i]=0;
}
for (int i = 0; i < 5; i++)
{
for(int i1=0;i1<100;i1++)
{
recstack[i1]=0;
visited[i1]=0;
}
if(dfs(g,i,visited,recstack))
{
cout<<" Cycle present ";
break;
}
}
return 0;
}
No comments:
Post a Comment