627 - The Net

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sohag144
New poster
Posts: 14
Joined: Mon Feb 27, 2006 4:12 pm
Location: Dhaka,Bangladesh
Contact:

627 - The Net

Post by sohag144 » Thu Nov 02, 2006 6:53 am

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
New poster
Posts: 3
Joined: Mon Feb 06, 2006 6:41 am

627 -RTE

Post by qazxcvbn » Thu Nov 09, 2006 5:52 pm

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
New poster
Posts: 14
Joined: Fri Aug 13, 2010 12:22 pm

kisuna

Post by faiem » Thu Jan 20, 2011 7:52 am

vul sobi vul
Last edited by faiem on Mon Mar 07, 2011 8:58 pm, edited 2 times in total.

faiem
New poster
Posts: 14
Joined: Fri Aug 13, 2010 12:22 pm

WA: 627 - The Net (Systemdown)

Post by faiem » Mon Mar 07, 2011 8:53 pm


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;
    }


jakir.duet
New poster
Posts: 4
Joined: Sat Nov 20, 2010 10:27 pm

627:Why WA???

Post by jakir.duet » Thu Apr 28, 2011 7:20 pm

Simple BFS......I did so.....but WA many times......why???

Code: Select all

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstdlib>
#include<cstring>
#define M 310
using namespace std;

int N,Path[M];
int List[M][55],adjNo[M];
bool BFS(int,int);
void PrintPath(int,int);

int main()
{
	int t,i,x,y;
	bool f;
	freopen("in.txt","r",stdin);

	while(scanf("%d",&N)==1)
	{
		memset(adjNo,0,sizeof(adjNo));
		for(i=1;i<=N;i++)
		{
			scanf("%d-%d",&x,&y);

			List[x][adjNo[x]++]=y;

			while(scanf(",%d",&y)==1)
				List[x][adjNo[x]++]=y;
		}

		scanf("%d",&t);
		printf("-----\n");
		for(i=1;i<=t;i++)
		{
			scanf("%d%d",&x,&y);
			f=BFS(x,y);

			if( f==false )
				printf("connection impossible\n");
			else
			{
				PrintPath(x,y);
				printf("\n");
			}
		}
	}
	return 0;
}

bool BFS(int src,int dest)
{
	int h,i,x,color[M];
	queue<int>Q;
	memset(color,0,sizeof(color));
	color[src]=1;Q.push(src);

	while(!Q.empty())
	{
		h=Q.front();Q.pop();
		for(i=0;i<adjNo[h];i++)
		{
			x=List[h][i];
			if(color[x]==0)
			{
				color[x]=1;
				Path[x]=h;
				if(x==dest){return true;}
				Q.push(x);
			}
		}
	}
	return false;
}

void PrintPath(int x,int y)
{
	if(x==y)
	{
		printf("%d",x);
		return;
	}
	PrintPath(x,Path[y]);
	printf(" %d",y);
}
Programming is a challenge........so as life.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 627:Why WA???

Post by sohel » Fri Apr 29, 2011 12:41 am

Search the board first using the 'search' button/text located at the top right corner.
There are plenty of discussions for your problem. Make you post in an existing thread.

jakir.duet
New poster
Posts: 4
Joined: Sat Nov 20, 2010 10:27 pm

Re: 627:Why WA???

Post by jakir.duet » Fri Apr 29, 2011 6:54 am

Absolutely not, there are 2/3 posts with no replies.....
Thanks Sohel vai for your responce.
Programming is a challenge........so as life.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 627:Why WA???

Post by sohel » Fri Apr 29, 2011 10:57 am

Hm, you are right. There aren't too many discussions for this problem. However, there is one thread - so next time, try to make your post on an existing one.

jakir.duet
New poster
Posts: 4
Joined: Sat Nov 20, 2010 10:27 pm

Re: 627:Why WA???

Post by jakir.duet » Fri Apr 29, 2011 4:51 pm

Thanks vaia again...........I'll remember your advice :)
Programming is a challenge........so as life.

sreka11
New poster
Posts: 15
Joined: Fri Aug 15, 2014 8:06 pm

Re: 627 - The Net

Post by sreka11 » Thu Sep 25, 2014 12:03 am

Can you give me some real test cases or show me why do I get a Runtime Error ?

Thanks.

Code: Select all

import java.util.*;
import java.io.*;

class Main
{	
	static Vector<Vector<Integer>> vect;
	static int[] dist;
	static int[] parent;
	static int s;
	static StringBuffer str;
	
	public static void main(String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
		
		str = new StringBuffer();
		
		String line = br.readLine();
		
		
		while(line != null)
		{
			int n = Integer.parseInt(line);
			
			vect = new Vector<Vector<Integer>>(n);
			
			for(int i = 0; i < n; i++)
			{
				Vector<Integer> v = new Vector<Integer>();
				vect.add(v);
			}
			
			for(int i = 0; i < n; i++)
			{
				line = br.readLine();
				
				int s1;
				
				String[] s2;
				
				
				if(line.length() > 2)
				{
					s1 = Integer.parseInt(line.substring(0, line.indexOf('-'))) - 1;
					s2 = line.substring(line.indexOf('-')+1, line.length()).split(",");
					
					for(int j = 0; j < s2.length; j++)
					{
						vect.get(s1).add(Integer.parseInt(s2[j])-1);
					}
				}
			}
			
			line = br.readLine();
			
			str.append("-----\n");
			
			int n2 = Integer.parseInt(line);
			
			for(int i = 0; i < n2; i++)
			{
				line = br.readLine();
				
				StringTokenizer sTok = new StringTokenizer(line);
				
				s = Integer.parseInt(sTok.nextToken()) - 1;
				
				int b = Integer.parseInt(sTok.nextToken()) - 1;
				
				Queue<Integer> q = new LinkedList<Integer>();
				
				dist = new int[n];
				parent = new int[n];
				
				Arrays.fill(dist, -1);
				
				q.add(s);
				
				dist[s] = 0;
				
				
				while(!q.isEmpty())
				{
					int v = q.poll();
					
					Iterator it = vect.get(v).iterator();
					
					while(it.hasNext())
					{
						int u = (int)it.next();
						
						if(dist[u] == -1)
						{
							dist[u] = dist[v] + 1;
							parent[u] = v;
							q.add(u);
						}
					}
				}
				
				if(dist[b] != -1)
					printPath(b);
				else
					str.append("connection impossible");
				
				str.append("\n");
			}
			
			line = br.readLine();
		}
			
		
		
		
		
		out.write(str.toString());
		
		out.flush();
	}
	
	public static void printPath(int v)
	{
		if(v == s)
		{
			str.append(s+1);
			return;
		}
		
		printPath(parent[v]);
		str.append(" " + (v+1));
	}
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 627 - The Net

Post by brianfry713 » Thu Sep 25, 2014 10:46 pm

Instead of filling up a StringBuffer with all of the output try writing directly to the BufferedWriter or at least between test cases.
Check input and AC output for thousands of problems on uDebug!

sreka11
New poster
Posts: 15
Joined: Fri Aug 15, 2014 8:06 pm

Re: 627 - The Net

Post by sreka11 » Thu Sep 25, 2014 11:19 pm

I am still getting a Runtime Error. I always fill the StringBuffer like this and it always works so I guess it is something else. I have tried a lot of changes but I still get Runtime Error.

moudud99
New poster
Posts: 28
Joined: Fri Feb 08, 2013 1:40 pm

Re: 627 - The Net

Post by moudud99 » Thu Oct 02, 2014 6:32 pm

Can someone help me with some I/O?
so that I can find my mistake.

Code: Select all

Be careful about INPUT!!!
Last edited by moudud99 on Fri Oct 03, 2014 8:06 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 627 - The Net

Post by brianfry713 » Fri Oct 03, 2014 1:57 am

sreka11, try input:

Code: Select all

10
1-
2-
3-
4-
5-
6-
7-
8-
9-
10-
1
1 2
Your issue is on line 47:
s2 = line.substring(line.indexOf('-')+1, line.length()).split(",");
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 627 - The Net

Post by brianfry713 » Fri Oct 03, 2014 2:00 am

moudud99, don't print a space at the end of a line.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 6 (600-699)”