Monday, 11 July 2016

Detecting cycle in an undirected graph

#include<bits/stdc++.h>
using namespace std;
int i,j,k,l,m,n;
struct edge
{
int u,v;
};
int pr[1009];
vector<edge>e;
int find(int r)
{
   return (pr[r]==r)?r:find(pr[r]);
}
bool cycle(int n)
{
for(i=1;i<=n;i++)
        pr[i]=i;
for(int i=0;i<(int)e.size();i++)
{
int u=find(e[i].u);
int v=find(e[i].v);
if(u!=v)
{
pr[u]=v;
}
else
            return false;
}
return true;
}

int main()
{
cin>>n>>m;
for(i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
edge get;
get.u=u;
get.v=v;
e.push_back(get);
}
if(cycle(n)==1)
        cout<<"No cycle exists"<<endl;
    else
        cout<<"Cycle exists"<<endl;
return 0;

}

No comments:

Post a Comment