I tried to but my complexity is O(V^2)… Each arr[i][j] tells me whether i and j are connected or not. This is my implementation
bool dfs(int start)
{
int i,j,t,parent;
pair <int,int>temp;
for(i=1;i<=V;i++)
{
bool hi=false;
for(j=1;j<=V;j++)
{
if(arr[i][j])hi=true;
}
if(hi==false)return true;
}
list < pair<int,int> > stk;
stk.push_front(make_pair(start,0));
vis[start]=true;
while(!stk.empty())
{
temp=stk.front();
t=temp.first;
parent=temp.second;
stk.pop_front();
for(i=1;i<=V;i++)
if(arr[t][i])
{
if(vis[i]==true && parent!=i)return true;
else if(vis[i])continue;
else stk.push_front(make_pair(i,t));
}
}
return false;
return false;
}