10305 - Ordering Tasks

[Achilies_Saiful_Buet]

WA!!!!!!!!!!!!!!!!!!! plz helpppppppp!!!!!
why'm getting WA??? I used DFS for topological sorting and for every input posted here i got the same output as like UVA toolkit..plzzzzz help me out

Code: Select all

ACCEPTED

[brianfry713]

input

Code: Select all

5 0
0 0

Output could be something like
1 2 3 4 5

[Achilies_Saiful_Buet]

thnx brianfry713 !!!i had a silly mistake in taking input....

[PromeNabid]

Got WA in this topo sort problem. I thought all possible valid outputs should be accepted. I just did a straight forward topological sort. I am not getting what to do with it. Thanks in advance.

Code: Select all

#include <iostream>
using namespace std;
int main ( ) {
           while( 1 ) {
                 printf( "Thanks, Brianfry. AC Now" );
          }
    return 0;
}

[brianfry713]

Input:

Code: Select all

2 1
1 2
2 1
2 1
0 0

AC output:

Code: Select all

1 2
2 1

[mobarak.islam]

Here I'm getting wrong answer. I checked all the i/o given in this board. Please Help.

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <memory>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;
void BFS_VISIT(int p);
int A[101];
int front;
int  end;
struct graph{
	int parent[101];
	int child[101];
	int count;
	int ccount;
	bool visited;
} node[101];

int main()
{
	int x,y,n,m;
	
	while(scanf("%d %d",&n,&m) && n && m)
	{
		memset(node,0,sizeof(node));
		memset(A,0,sizeof(A));
		for(int i=0;i<m;i++)
		{
			scanf("%d %d",&x,&y);
			node[y].parent[node[y].count++]=x;
			node[x].child[node[x].ccount++]=y;
		}

		for(int i=1;i<=n;i++)
		{
			if(node[i].visited == false && node[i].count == 0 && node[i].ccount == 0 )
			{
				node[i].visited = true;
				printf("%d ",i);

			}
			if(node[i].visited == false && node[i].count == 0 && node[i].ccount != 0)
			{
				front=0;
				end=0;
				printf("%d ",i);
				BFS_VISIT(i);

			}
			

		}
		printf("\n");
	}



	return 0;
}

void BFS_VISIT(int p)
{
	node[p].visited = true;
	for(int k=node[p].ccount;k>0;k--)
	{
		A[end++]= node[p].child[(k-1)];

		for(int j = node[node[p].child[(k-1)]].count;j>0;j--)
		{
			if(node[node[node[p].child[(k-1)]].parent[j-1]].visited == false)
			{
				printf("%d ",node[node[p].child[(k-1)]].parent[j-1]);
				node[node[node[p].child[(k-1)]].parent[j-1]].visited = true;
			}


		}
		if(node[node[p].child[k-1]].visited == false)
		{
			printf("%d ",node[p].child[k-1]);
			node[node[p].child[k-1]].visited =true;
		}


	}
	while(front!=end)
	{
		BFS_VISIT(A[front++]);

	}



}

[brianfry713]

For input:

Code: Select all

1 0
0 0

Output should be:

Code: Select all

1

[mobarak.islam]

@Brianfry713: I resolved the problem but still getting wrong answer :

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <memory>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;
void BFS_VISIT(int p);
int A[101];
int front;
int  end;
struct graph{
	int parent[101];
	int child[101];
	int count;
	int ccount;
	bool visited;
} node[101];

int main()
{
	int x,y,n,m;
	
	while(scanf("%d %d",&n,&m) && (n ||m))
	{
		memset(node,0,sizeof(node));
		memset(A,0,sizeof(A));
		for(int i=0;i<m;i++)
		{
			scanf("%d %d",&x,&y);
			node[y].parent[node[y].count++]=x;
			node[x].child[node[x].ccount++]=y;
		}

		for(int i=1;i<=n;i++)
		{
			if(node[i].visited == false && node[i].count == 0 && node[i].ccount == 0 )
			{
				node[i].visited = true;
				printf("%d ",i);

			}
			if(node[i].visited == false && node[i].count == 0 && node[i].ccount != 0)
			{
				front=0;
				end=0;
				printf("%d ",i);
				BFS_VISIT(i);

			}
			

		}
		printf("\n");
	}



	return 0;
}

void BFS_VISIT(int p)
{
	node[p].visited = true;
	for(int k=node[p].ccount;k>0;k--)
	{
		A[end++]= node[p].child[(k-1)];

		for(int j = node[node[p].child[(k-1)]].count;j>0;j--)
		{
			if(node[node[node[p].child[(k-1)]].parent[j-1]].visited == false)
			{
				printf("%d ",node[node[p].child[(k-1)]].parent[j-1]);
				node[node[node[p].child[(k-1)]].parent[j-1]].visited = true;
			}


		}
		if(node[node[p].child[k-1]].visited == false)
		{
			printf("%d ",node[p].child[k-1]);
			node[node[p].child[k-1]].visited =true;
		}


	}
	while(front!=end)
	{
		BFS_VISIT(A[front++]);

	}



}

[brianfry713]

Don't print a space at the end of the line.

[mobarak.islam]

@Brianfry713: I resolved the spacing problem but still getting wrong answer :

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <memory>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;
void BFS_VISIT(int p);
int A[101];
int front;
int  end;
struct graph{
   int parent[101];
   int child[101];
   int count;
   int ccount;
   bool visited;
} node[101];

int main()
{
   int x,y,n,m;
   bool des;
   
   while(scanf("%d %d",&n,&m) && (n ||m))
   {
	   des=true;
      memset(node,0,sizeof(node));
      memset(A,0,sizeof(A));
      for(int i=0;i<m;i++)
      {
         scanf("%d %d",&x,&y);
         node[y].parent[node[y].count++]=x;
         node[x].child[node[x].ccount++]=y;
      }

      for(int i=1;i<=n;i++)
      {
         if(node[i].visited == false && node[i].count == 0 && node[i].ccount == 0 )
         {
			 
            node[i].visited = true;
			if(des)
				printf("%d ",i);
			else
				printf(" %d",i);
			des=false;

         }
         if(node[i].visited == false && node[i].count == 0 && node[i].ccount != 0)
         {
            front=0;
            end=0;
			if(des)
				printf("%d ",i);
			else
				printf(" %d",i);
			des=false;
            BFS_VISIT(i);

         }
         

      }
      printf("\n");
   }



   return 0;
}

void BFS_VISIT(int p)
{
   node[p].visited = true;
   for(int k=node[p].ccount;k>0;k--)
   {
      A[end++]= node[p].child[(k-1)];

      for(int j = node[node[p].child[(k-1)]].count;j>0;j--)
      {
         if(node[node[node[p].child[(k-1)]].parent[j-1]].visited == false)
         {
            printf(" %d",node[node[p].child[(k-1)]].parent[j-1]);
            node[node[node[p].child[(k-1)]].parent[j-1]].visited = true;
         }


      }
      if(node[node[p].child[k-1]].visited == false)
      {
         printf(" %d",node[p].child[k-1]);
         node[node[p].child[k-1]].visited =true;
      }


   }
   while(front!=end)
   {
      BFS_VISIT(A[front++]);

   }



}

[brianfry713]

For the sample input, a correct output is:

Code: Select all

1 4 2 5 3

Your code is printing an extra space after the first number

Code: Select all

1  5 2 3 4

[LazyTym]

Code: Select all

#include<iostream>
#include<cstdio>
#include<stack>
#include<map>
#include<cstring>
#include<vector>


using namespace std;


int visited[100];
vector < vector<int> >L(100);
int m,n;
stack<int>stk;


void topologicalUtil(int k)
{
    visited[k]=1;
    for(int i=0;i<L[k].size();i++)
    {
        if(visited[L[k][i]]==0)
        {
            topologicalUtil(L[k][i]);
        }
    }
    stk.push(k);
}

void topologicalSort()
{

    for(int i=0;i<100;i++) visited[i]=0;
    for(int i=1;i<=n;i++)
    {
        if(visited[i]==0)
        {
            topologicalUtil(i);
        }
    }
    while(stk.empty()==false)
    {
        cout<<stk.top()<<" ";
        stk.pop();
    }
    cout<<endl;

}

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

    int a,b;
    while(1)
    {
        for(int i=0;i<100;i++) L[i].clear();
        cin>>n>>m;
        if(n==0 && m==0) break;
        for(int i=0;i<m;i++)
        {
            cin>>a>>b;
            L[a].push_back(b);
        }
        topologicalSort();
    }
    return 0;
}

[lighted]

If there is a thread about your problem, please use it.
Don't open new thread. Use search first by problem number (10305 for this problem)
http://acm.uva.es/board/search.php?keywords=10305

For this problem there is existing thread
http://acm.uva.es/board/viewtopic.php?f ... ilit=10305
You can check your program for input/output tests posted here.

To avoid Runtime error you must increase arrays parameter

Code: Select all

int visited[100];
vector < vector<int> >L(100);

It must be

Code: Select all

int visited[101];
vector < vector<int> >L(101);

To get acc you must also increase this

Code: Select all

for(int i=0;i<100;i++) visited[i]=0;

It must be

Code: Select all

for(int i=0;i<=100;i++) visited[i]=0;

and

Code: Select all

for(int i=0;i<100;i++) L[i].clear();

It must be

Code: Select all

for(int i=0;i<=100;i++) L[i].clear();

[uDebug]

Replying to follow the thread.

[Mohammad Erfan]

Correct answer:
1 2 5 6 9 3 4 8 7 12 10 11