Dfs print all the nodes

1

whats wrong with this code I am trying to print all the nodes with dfs??

#define ll long long 
#define mod 1000000007 
using namespace std; 
ll m,n,u,v;
bool vis[100000]={false};
vector<ll>adj[100000];
 void dfs(ll u)
{
     vis[u]=true;
     cout<<u<<"->";
     for(ll i=0;i<adj[u].size();i++)
     {
          if(!vis[adj[u][i]])
          {
               dfs(adj[u][i]);
          }
     }
}
 int main()
 {
     ios_base::sync_with_stdio(0);
     cin.tie(0);
     cin>>n>>m;
     //n=number of nodes m=number of edges
     while(m--);
     {
         cin>>u>>v;
         adj[u].push_back(v);
         adj[v].push_back(u);
     }
     dfs(1);
     return 0;
 }```
2

is it a connected graph? if not there is a chance that 1 is not connected to any other node.

1 Like
3

You can refer to this code for disconnected graph

4

Please use preformatted text for codes. Just use ``` before and after the code and see the magic.

His code goes something like this:

#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
ll m,n,u,v;
bool vis[100000] = {false};
vector<ll> adj[100000];
void dfs(ll u) {
    vis[u] = true;
    cout << u << "->";
    for(ll i = 0; i < adj[u].size(); i++) {
        if(!vis[adj[u][i]]) {
             dfs(adj[u][i]);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    while(m--); {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);
    return 0;
}

There are 3 mistakes in the code:

Mistake 1:

When the graph is disconnected.
All the nodes aren’t being visited.

Key to solve this problem

Make the following change:
From

dfs(1);

To:

for(ll i = 1; i <= n; i++) {
    if(!vis[i]) {
        dfs(i);
    }
}
Mistake 2:

If n = 100000, then you will get RE(SIGSEGV).

Key to solve this problem

From:

bool vis[100000] = {false};
vector<ll> adj[100000];

To:

bool vis[100010] = {false};
vector<ll> adj[100010];
Mistake 3:

According to the code you have posted, only one edge will be taken every time you run, not m edges.

Key to solve this

Remove the semicolon in while loop. Putting the semicolon makes it a null loop, just adding to the time complexity of your program, but doing nothing.

1 Like
5

i have made some changes

#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define N 100000
using namespace std;
ll m,n,u,v;
bool vis[N] = {false};
vector<ll> adj[100000];
void dfs(ll u) 
{
    vis[u] = true;
    cout << u <<" ";
    for(ll child:adj[u]) 
    {
        if(!vis[child])
        {
             dfs(child);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    while(m--)
    {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);
    return 0;
}
1 Like
6

thanks for the help

7

Yes, this looks fine. Just go through the first two mistakes(not the last one) I pointed out. Try not seeing the key to correct that mistake first. First try, and then see it.