-1

I am trying to solve the problem using the adjacency list now. But the problem I am facing here is when I am trying to insert the element in an adjacency list, it stores the value in the sequence I have entered. For example for the test case:

5 8 0 1 0 4 1 2 2 0 2 4 3 0 3 2 4 3

My output is:

0 1 4 2 3

Expected output is:

0 1 2 3 4.

It is because my adjacency list stores the value in the fashion it was not entered in a sorted manner. How would I store it in a sorted manner? If I sort it, it just increases the complexity of the code. Please help.

#include<bits/stdc++.h>
using namespace std; 
typedef long long int ll;

void addEdge(vector<ll> edges[], ll u, ll v)
{
    edges[u].push_back(v);
    edges[v].push_back(u);
}

void BFS(vector<ll> edges[], ll v, bool * visited, queue<ll> q)
{
    while(!q.empty())
    {
        ll s = q.front();
        cout << s << " ";
        q.pop();
        for(ll i = 0; i < edges[s].size(); i++)
        {
            if(!visited[edges[s][i]])
            {
                visited[edges[s][i]] = true;
                q.push(edges[s][i]);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll v, e;
    cin >> v >> e;

    vector<ll> edges[v];
    for(ll i = 0 ; i < e; i++)
    {
        int x, y;
        cin >> x >> y;
        addEdge(edges, x, y);
    }

    bool * visited = new bool[v];
    memset(visited, false, sizeof(visited));
    queue<ll> q;
    q.push(0);
    visited[0] = true;

    BFS(edges, v, visited, q);
    return 0;
}
paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
Sourabh
  • 53
  • 1
  • 11
  • From your question it is not clear what the output order should be in a general case. What is the "right" output? – Evg Oct 25 '19 at 10:14
  • You should *never* `#include `. It is not proper C++. It ruins portability and fosters terrible habits. Questions using it will usually be downvoted on Stack Overflow. See [Why should I not `#include `](https://stackoverflow.com/q/31816095). Incidentally, please try to avoid `using namespace std;` because it is considered bad practice. See [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/q/1452721) The `ll` shorthand should also be removed because it exists for obfuscation only. – L. F. Oct 25 '19 at 10:17
  • Now, questions seeking debugging help ("why isn't this code working?") must include the desired behavior, a *specific problem or error* and *the shortest code necessary* to reproduce it *in the question itself*. Questions without *a clear problem statement* are not useful to other readers. You need to debug your code and create a [mre]. – L. F. Oct 25 '19 at 10:19

1 Answers1

0

Yes, you were right, the behaviour is due to the order in the input. You could try using a priority queue instead of a simple vector for your adjacency list, to keep your vertices in a specific order, but this does add complexity to your algorithm.

Nándor Csereoka
  • 1
  • 2