280 - Vertex

[brianfry713]

Don't read from a file.

[lighted]

Post here code which you submit. In posted code above you read from file. Why do you use buffstr? You could work only with integers to avoid possible bugs because of strings. Sent you PM.

[richatibrewal]

I am continuosly getting WA for the following code. I am using BFS and adjacency list in my algorithm. It is giving the right output for all the sample cases given in this forum.

Code: Select all

#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;

typedef struct linked_list
{
    int data;
    struct linked_list *add;
}node;

node *head[110];

void create(node **header,int a,int b)
{
    if((*header)==NULL)
    {
        *header=(node *)malloc(sizeof(node));
        (*header)->data=a;
        (*header)->add=(node *)malloc(sizeof(node));
        (*header)->add->data=b;
        (*header)->add->add=NULL;
        return;
    }

    node *current;
    current=*header;
    while(current->add!=NULL)
    {
        current=current->add;
        if(current->data == b)
            return;
    }
    current->add=(node *)malloc(sizeof(node));
    current->add->data=b;
    current->add->add=NULL;

}

void find_vertex(int v,int n)
{
    bool visited[110];
    int i,j=n;
    queue<int> q;
    node *current;

    for(i=1;i<=n;i++)
        visited[i]=false;

    q.push(v);
  //  visited[v]=true;

    while(!q.empty())
    {
        v=q.front();
        q.pop();
        if(head[v]==NULL)
            break;
        for(current=(head[v])->add;current!=NULL;current=current->add)
        {
            i=current->data;
            if(!visited[i])
            {
              //  printf("hii");
                n--;
                visited[i]=true;
                q.push(i);
            }
        }
    }

    printf("%d",n);
    for(i=1;i<=j;i++)
        if(!visited[i])
            printf(" %d",i);
    printf("\n");
}

int main()
{
   // node *head[110];
    int n,m,a,b,v,i;

    while(scanf("%d",&n)!=EOF && n)
    {

        for(i=1;i<=n;i++)
            head[i]=NULL;

        while(scanf("%d",&a)!=EOF && a)
        {
            while(scanf("%d",&b)!=EOF && b)
            {
                create(&head[a],a,b);
            }
        }

       /* node *current;
        for(i=1;i<=n;i++)
        {
            if(head[i]==NULL)
            {
                printf("%d no edges\n",i);
                continue;
            }
            current=head[i];
            while(current!=NULL)
            {
                printf("%d ",current->data);
                current=current->add;
            }
            printf("\n");
        }*/
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d",&v);
            find_vertex(v,n);
        }

    }

    return 0;
}

[brianfry713]

Input:

Code: Select all

3
2 3 0
3 1 2 0
0
3 1 2 3
8
2 3 4 8 0
3 1 6 0
4 3 5 7 0
5 2 3 6 8 0
6 1 3 4 5 0
7 1 3 5 6 0
8 2 3 4 5 0
0
8 1 2 3 4 5 6 7 8
4
1 2 4 0
2 3 0
3 1 2 4 0
4 1 2 0
0
4 1 2 3 4
1
0
1 1
9
1 6 8 0
2 1 4 6 9 0
3 2 4 5 8 9 0
4 5 7 0
5 1 3 4 8 9 0
6 2 3 4 5 7 9 0
7 1 2 3 4 0
8 1 2 3 4 6 9 0
9 1 2 5 7 0
0
9 1 2 3 4 5 6 7 8 9
8
1 2 3 8 0
2 1 3 5 6 7 8 0
3 4 0
4 1 3 0
5 1 3 7 8 0
6 2 4 7 8 0
7 6 0
8 4 6 7 0
0
8 1 2 3 4 5 6 7 8
9
1 3 4 0
2 1 4 5 9 0
3 4 7 8 0
4 1 2 5 6 7 8 9 0
5 1 3 4 8 9 0
6 2 3 5 7 8 9 0
7 2 3 8 9 0
8 2 4 6 9 0
9 1 2 3 5 7 0
0
9 1 2 3 4 5 6 7 8 9
10
1 7 9 10 0
2 3 4 5 7 0
3 1 2 8 10 0
4 3 5 0
5 1 3 6 0
6 1 2 7 10 0
7 8 9 0
8 1 2 3 4 5 6 9 0
9 2 3 5 8 0
10 1 2 4 7 0
0
10 1 2 3 4 5 6 7 8 9 10
10
1 2 4 5 6 0
2 1 5 6 7 10 0
3 2 4 6 8 9 0
4 2 3 5 7 9 0
5 1 3 4 6 7 8 0
6 1 3 5 9 10 0
7 6 8 9 0
8 2 3 4 6 9 0
9 1 2 3 4 6 0
10 1 3 6 7 8 9 0
0
10 1 2 3 4 5 6 7 8 9 10
7
1 5 0
2 4 0
3 1 2 4 6 0
4 1 2 3 0
5 4 6 7 0
6 5 0
7 2 5 0
0
7 1 2 3 4 5 6 7
0

AC output:

Code: Select all

3 1 2 3
0
0
8 1 2 3 4 5 6 7 8
0
0
0
0
0
0
0
0
0
0
0
1 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

[uDebug]

Replying to follow the thread.

[samir_h]

All the test cases in discussion board match in uDebug.
But still WA.
Please check my code: http://ideone.com/gbgMwN

And suggest what to do.