Unreachable Nodes DFS

general
,
1

This is the problem link Unreachable Nodes

This is my code ideone
It passes one test case and fails in another. Can anyone help in finding error in my logic?

2

If I am not wrong, the Q asks for the nodes which cannot be reached from entry node. Although I have no experience in graph theory, and cannot provide you with a code soln, I can offer a sample case.

Input-
5 3
8 1
8 2
4 3
8
Expected output-
2

Your output-
0

The picture

Nodes are as-

4-3 2-8-1

So, 4 and 3 cannot be reached from 8. Try and see if fixing this test case helps! Cheers and all the best :slight_smile:

1 Like
3

What I can see is that when you are taking the entry node,
cin >> n, you should also do n-- as previous nodes are also 0-based.

Also , c is the number of nodes that have been visited, not unreachable.
For that just iterate through the visited array after doing dfs and count number of false entries.However , be sure to just iterate through the first n elements.

1 Like
4

As question says we need to find the unvisited nodes from the head node! So firstly we have to perform DFS and visit all the vertices that are reachable from head! After performing DFS yo just need to count Unvisited nodes i.e., the nodes that are still false (Visited[i] = false) i={0,1,2,…nodes) …

I just made some changes in your code! See this AC code

  #include<iostream>
    #include<vector>
    using namespace std;
    vector<int>adj[100000];
    bool visited[100000];
    int c=0;
    void initialize()
    {
        for(int i=0;i<100000;i++)
            visited[i] = false;
    }
    void dfs(int s)
    {
        visited[s] = true;
        for(size_t i=0; i<adj[s].size(); i++)
        {
            if(visited[adj[s][i]] == false)
                {
                   
                    dfs(adj[s][i]);
                }
        }
    }
     
    int main()
    {
        int nodes,edges,x,y,n;
        cin>>nodes>>edges;
        for(int i=0;i<edges;i++)
        {
            cin>>x>>y;
            x--;y--;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        initialize();
        cin>>n;
        --n;
        dfs(n);
        for(int i=0;i<nodes;++i)
        {
            if(!visited[i])
                ++c;
        }
        cout<<c;
        return 0;
    }
1 Like
5

PS: Any1 seeing this-

I actually want to know how do I post comments? In other’s answers? I want to ask Q but I am stuck with 1 karma (and idk how long it will continue) and I cant see any feature to PM either. So, plz help :slight_smile:
Incase its against rules, do comment and let me know. I will edit/delete. But if possible, do help :slight_smile:

6

I guess you need karma more than 50… Usually upvotes and accepted answers fetches you karma… I am upvoting your comment to give you some :slight_smile:

7

Thank you mate, It worked :slight_smile:

1 Like
8

Thanks! :slight_smile:

9

Thankkkks :))))) !!!