# How to implement DFSusing adjacency matrix in O(m+n)

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;
``````

}

You can’t make it run in O(N+M) with adjacency matrix, because you’ll have to look at every element of this matrix. You should use adjacency list instead.

1 Like

Using adjacency matrix is not an efficient way to store graph because the complexity of graph traversal can go up till O(n*2) . Use adjacency list instead.

1 Like

Thanks mate!

Yeah I know that but I wished to do so! and was seeking help for a code with same complexity(I thought there existed such a code!)

for implementing DFS u will need to know about all the edges and for that if u use adj matrix then its done in O(n^2) if u want u do it better try using adj list

1 Like