627 - The Net

[sohag144]

I cant understand why i got RE?

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<stack>
using namespace std;

#define MAXV 300
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define NIL -1
#define INF -99

int color[MAXV+1];
int discover[MAXV+1];
int parent[MAXV+1];
int path;
queue<int> Q;

struct edge
{
   vector<int> eg;
};

struct graph
{
   edge e[MAXV+1];
   int degree[MAXV+1];
   int nvertices;
}g;

void initialize_graph()
{
   int i;
   
   g.nvertices=0;
   for(i=1; i<=MAXV; i++)
   {
      g.degree[i]=0;
      g.e[i].eg.clear();
   }
   //vector must be empty
}

void insert_edge(int x,int y)
{
   g.e[x].eg.push_back(y);
   g.degree[x]++;
}

void get_edge(char *s,int x)
{
   int i,j,l,y;
   char t[10];

   i=0;
   while(s[i]!='-')i++;
   l=strlen(s);
   for(i; i<l; i++)
   {
      if(s[i]>='0' && s[i]<='9')
      {
         j=0;
         while((s[i]>='0' && s[i]<='9'))
         {
            t[j++]=s[i++];
         }
         t[j]=0;
         y=atoi(t);
         insert_edge(x,y);
      }      
   }
}

void read_graph(int n)
{
   int i;
   char s[100];

   initialize_graph();

   g.nvertices=n;

   for(i=1; i<=n; i++)
   {
      gets(s);

      get_edge(s,i);
   }

}

void bfs(int source)
{
   int u,v,i;

   for(u=1; u<=g.nvertices; u++)
   {
      color[u]=WHITE;
      discover[u]=INF;
      parent[u]=NIL;      
   }

   color[source]=GRAY;
   discover[source]=0;
   parent[source]=NIL;

   if(!Q.empty())
   {
      while(!Q.empty())
      {
         Q.pop();
      }
   }

   Q.push(source);

   while(!Q.empty())
   {
      u=Q.front();
      Q.pop();

      for(i=1; i<=g.degree[u]; i++)
      {
         v=g.e[u].eg[i-1];

         if(color[v]==WHITE)
         {
            color[v]=GRAY;
            discover[v]=discover[u]+1;
            parent[v]=u;

            Q.push(v);
         }
      }
      color[u]=BLACK;
   }
}

void find_path(int start,int end)
{
   if(start==NIL || end==NIL)
   {
      printf("connection impossible");
      path=0;
   }
   else if(start==end)
      printf("%d ",start);
   else
   {
      find_path(start,parent[end]);
      if(path)printf("%d ",end);
   }
}

void main()
{
   int m,n,i,j,k,source,destination;
   char s[200];

   freopen("in.txt","r",stdin);

   while(gets(s))
   {
      n=atoi(s);

      if(n)
      read_graph(n);

      /*
      for(i=1; i<=n; i++)
      {
         printf("%d-",i);
         for(j=0; j<g.degree[i]; j++)
         {
            printf("%d ",g.e[i].eg[j]);
         }
         printf("\n");
      }
      */
      gets(s);
      m=atoi(s);

      if(m)printf("-----\n");
      for(k=0; k<m; k++)
      {
         gets(s);
         sscanf(s,"%d %d",&source,&destination);

         bfs(source);

         path=1;
         find_path(source,destination);
         printf("\n");
      }
   }
}


[qazxcvbn]

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define len 301


int main()
{
   int map[len][len];
   int n,i,j,k,node,node1,count,count2;
   char str[1000],*str2;
   int path[len][len][100];
   while(scanf("%d",&n)==1)
   {
      count2=0;
      count=0;
      for(i=1;i<=n;i++)
      {
         for(j=1;j<=n;j++)
         {
            if(i==j)
               map[i][j]=0;
            else
               map[i][j]=-1;
            for(k=0;k<100;k++)
            {
               path[i][j][k]=-1;
            }
         }
      }
      for(i=1;i<=n;i++)
      {
         scanf("%s",str);
         strtok(str,"-");
         str2=strtok(NULL,",");
         while(str2!=NULL)
         {
            node=atoi(str2);
            map[i][node]=1;
            path[i][node][0]=i;
            path[i][node][1]=node;
            str2=strtok(NULL,",");
         }
      }
      for(k=1;k<=n;k++)
      {
         for(i=1;i<=n;i++)
         {
            for(j=1;j<=n;j++)
            {
               if(map[i][k]!=-1 && map[k][j]!=-1)
               {
                  if(map[i][k]+map[k][j]<map[i][j] || map[i][j]==-1)
                  {
                     map[i][j]=map[i][k]+map[k][j];
                     count=0;
                     while(path[i][k][count]!=-1)
                     {
                        path[i][j][count]=path[i][k][count];
                        count++;
                     }
                     count2=1;
                     while(path[k][j][count2]!=-1)
                     {
                        path[i][j][count]=path[k][j][count2];
                        count++;
                        count2++;
                     }
                  }
               }
            }
         }
      }
      scanf("%d",&n);
      printf("-----\n");
      for(i=0;i<n;i++)
      {
         scanf("%d %d",&node,&node1);
         if(path[node][node1][0]==-1)
            printf("connection impossible\n");
         else
         {
            printf("%d",path[node][node1][0]);
            for(j=1;j<=map[node][node1];j++)
            {
               printf(" %d",path[node][node1][j]);
            }
            printf("\n");
         }
      }
   }
   return 0;
}



I don't have any idea about what problem makes me RE.
Who can answer me???
or give me some test data.
Thanks for your help!!

[faiem]

vul sobi vul

[faiem]

Why i got WA everytime...I think its a very simple BFS.

Code: Select all

#include<cstdio>
#include<stack>
#include<queue>
#include<set>
using namespace std;

class Net{

    private:

    long I,J,path[305],m,n,sou,des,test;
    queue<long> Q;
    stack<long> P;
    set<long> s[305];
    set<long>::iterator it;
    bool flag[305];


    public:

    bool Reset(long N)
    {
        for(long I=0;I<=N;I++)
        {
            path[I]=0;
            flag[I]=0;
            }
        while(!Q.empty())
            Q.pop();
        while(!P.empty())
            P.pop();
        return 0;
        }

    bool input(long node)
    {
        Reset(node); //reset all array;
        for(long I=0;I<node;I++)
        {
            scanf("%ld",&m);
            while(scanf("%ld",&n)==1)
            {
                if(n<0)
                n=-n;
                s[m].insert(n);
                if(getchar()=='\n')
                    break;
                }

            }
          scanf("%ld",&test);
          printf("-----\n");
          while(test--)
          {
              scanf("%ld %ld",&sou,&des);
              BFS(sou,des);
              Reset(node);
              }

       // print(node);  //print adj_list;
        return 0;
        }

    bool print(long N)
    {
        for(long I=1;I<=N;I++)
        {
            printf("%ld->",I);
            for(it=s[I].begin();it!=s[I].end();it++)
                printf("%ld ",*it);
            printf("\n");
            }

        return 0;
        }

    bool graph_traversal(long node,long D)
    {
        for(it=s[node].begin();it!=s[node].end();it++)
        {
            if(flag[*it]==0)
            {
                Q.push(*it);
                flag[*it]=1;
                path[*it]=node;

                if(*it==D)    //if found destination return 1;
                    return 1;
                }
            }

        return 0;
        }

    bool BFS(long S,long D) S=Source...,D=destination
    {
        long F,K;
        Q.push(S);
        flag[S]=1;
        path[S]=-1;

        if(S==D)    //if Source = Destination
            {
                printf("%ld\n",S);
                Q.pop();
                return 0;
                }

        while(!Q.empty())
        {
            F=Q.front();
            Q.pop();
            if( graph_traversal(F,D) )  //if graoh _traversal  return 1...that means it found the destination.
                break;
            }

        if(flag[D]==0)
            printf("connection impossible\n");
        else
        {
            K=D;
            P.push(K);
            while(path[K]!=-1)
                {

                    K=path[K];
                    P.push(K);
                    }
            while(P.size()>1)
            {
                printf("%ld ",P.top());
                P.pop();
                }
            printf("%ld\n",P.top());
            P.pop();
            }

        return 0;
        }

    };


int main()
{
    long N;

    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    while(scanf("%ld",&N)==1)
    {
        Net Gp;
        Gp.input(N);
        }
    return 0;
    }