OJ Board

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

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

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

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

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

Code: Select all

Be careful about INPUT!!!

Code: Select all

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