Thursday, July 23, 2015

detect cycle in graph

#include <iostream>
#include <vector>
#include<fstream>
#include <list>
using namespace std;
int arrr[20],counter=0;
bool DFS(int s,vector < vector < int > > v,bool c[200],bool rec[100])
{
if(!c[s])
{
std::vector<int > ::iterator it;
rec[s]=true;
c[s]=true;
for(it=v[s].begin();it!=v[s].end();++it)
{
if(!c[*it]&&DFS(*it,v,c,rec))
return true;
else if(rec[*it])
return true;
}

}
rec[s]=false;
return false;
}
int main()
{
vector < vector <  int >  > v;
bool c[200],rec[100];
for (int i = 0; i < 200; i++)
{
c[i]=false;
rec[i]=false;
}
ifstream fin;
fin.open("/home/pawan/Desktop/input1.txt");
if(!fin.is_open())
{
cout<<" file not open";
return 0;
}

int n;
fin>>n;
v.resize(n);
int i,j,w;

while(!fin.eof())
{
fin>>i>>j>>w;
v[i].push_back(j);
}
for (i = 0; i < v.size(); i++)
{
std::vector<int >::iterator it;
cout<<i<<"-> ";
for(it=v[i].begin();it<v[i].end();it++)
cout<<*it<<" ";
cout<<endl;
}
bool result= DFS(1,v,c,rec);
if(result)
cout<<"cycle exist";
else
cout<<"cycle free";
return 0;

}

No comments:

Post a Comment

Contributors

Translate