Thread: BFS function problem

  1. #1
    Registered User
    Join Date
    Mar 2011
    Posts
    3

    BFS function problem

    The program returns me 1. I think that there is a mistake in one of the cycles. But I cant find where.
    Code:
    #include<iostream>
    #include<vector>
    #include<queue.h>
    
    #define NMAX 1024
    
    using namespace std;
    
    vector <int> a[NMAX];
    int n;
    int s[NMAX];
    void input()
    {
    int m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    int u,v;
    cin>>u>>v;
    a[u].push_back(v);
    a[v].push_back(u);
    }
    }
    int used[100];
    void bfs(int u)
    {
    queue<int>q;
    q.push(u);
    
    while(!q.empty())
    {
    u=q.front();
    q.pop();
    cout<<u<<" ";
    for(int j=0;j<a[u].size();j++)
    {
    int v=a[u][j];
    if(s[v]==0);
    s[v]=1;
    }
    
    }
    
    cout<<endl;
    }
    
    
    int main()
    {
    input();
    bfs(1);
    return 0;
    
    }

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Indent your code, please.
    Remove global variables.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    At least he provided a compilable example. It looks like a contest problem.
    Anyway, I autoformatted it, compiled, and ran.
    You could give at least an example of input, which produces incorrect result.
    Last edited by kmdv; 03-07-2011 at 08:38 AM.

  4. #4
    Registered User
    Join Date
    Mar 2011
    Posts
    3
    Try to input
    3 3
    1 3
    1 2
    3 1
    I think that the result is incorrect.

  5. #5
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    Code:
    if(s[v]==0);
    s[v]=1;
    1. The first semicolon must be removed
    2. You don't push vertices, which are connected to 'u', onto the queue (except 'u' itself at the beginning).

  6. #6
    Registered User
    Join Date
    Mar 2011
    Posts
    3
    Thak you. Now it's working.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Tough problem with function pointers
    By Montejo in forum C Programming
    Replies: 10
    Last Post: 12-22-2009, 01:17 AM
  2. Problem with Visual C++ Object-Oriented Programming Book.
    By GameGenie in forum C++ Programming
    Replies: 9
    Last Post: 08-29-2005, 11:21 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Problem with function pointers
    By vNvNation in forum C++ Programming
    Replies: 4
    Last Post: 06-13-2004, 06:49 AM
  5. structure vs class
    By sana in forum C++ Programming
    Replies: 13
    Last Post: 12-02-2002, 07:18 AM