10305 - Ordering Tasks

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

Moderator: Board moderators

Achilies_Saiful_Buet
New poster
Posts: 16
Joined: Wed Mar 28, 2012 7:24 pm
Location: Dhaka,Bangladesh

Re: 10305 - Ordering Tasks

Post by Achilies_Saiful_Buet » Mon Apr 16, 2012 7:21 pm

WA!!!!!!!!!!!!!!!!!!! :x :x :x 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
Last edited by Achilies_Saiful_Buet on Tue Apr 17, 2012 7:27 am, edited 1 time in total.

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

Re: 10305 - Ordering Tasks

Post by brianfry713 » Tue Apr 17, 2012 1:05 am

input

Code: Select all

5 0
0 0
Output could be something like
1 2 3 4 5
Check input and AC output for thousands of problems on uDebug!

Achilies_Saiful_Buet
New poster
Posts: 16
Joined: Wed Mar 28, 2012 7:24 pm
Location: Dhaka,Bangladesh

Re: 10305 - Ordering Tasks

Post by Achilies_Saiful_Buet » Tue Apr 17, 2012 7:29 am

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

PromeNabid
New poster
Posts: 21
Joined: Mon Jun 18, 2012 12:52 am
Location: Dhaka, Bangladesh.
Contact:

Re: 10305 - Ordering Tasks

Post by PromeNabid » Fri Jan 18, 2013 10:51 pm

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;
}
Last edited by PromeNabid on Sun Jan 20, 2013 3:23 pm, edited 1 time in total.

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

Re: 10305 - Ordering Tasks

Post by brianfry713 » Sat Jan 19, 2013 1:33 am

Input:

Code: Select all

2 1
1 2
2 1
2 1
0 0
AC output:

Code: Select all

1 2
2 1
Check input and AC output for thousands of problems on uDebug!

mobarak.islam
New poster
Posts: 38
Joined: Wed Dec 05, 2012 11:29 pm

Re: 10305 - Ordering Tasks

Post by mobarak.islam » Thu Dec 05, 2013 1:11 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10305 - Ordering Tasks

Post by brianfry713 » Thu Dec 05, 2013 11:21 pm

For input:

Code: Select all

1 0
0 0
Output should be:

Code: Select all

1
Check input and AC output for thousands of problems on uDebug!

mobarak.islam
New poster
Posts: 38
Joined: Wed Dec 05, 2012 11:29 pm

Re: 10305 - Ordering Tasks

Post by mobarak.islam » Fri Dec 06, 2013 7:23 am

@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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10305 - Ordering Tasks

Post by brianfry713 » Fri Dec 06, 2013 9:38 pm

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

mobarak.islam
New poster
Posts: 38
Joined: Wed Dec 05, 2012 11:29 pm

Re: 10305 - Ordering Tasks

Post by mobarak.islam » Sat Dec 07, 2013 8:32 pm

@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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10305 - Ordering Tasks

Post by brianfry713 » Tue Dec 10, 2013 12:44 am

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
Check input and AC output for thousands of problems on uDebug!

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

10305 - Ordering Tasks!!! why runtime error?

Post by LazyTym » Sun Jul 13, 2014 6:08 pm

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10305 - Ordering Tasks!!! why runtime error?

Post by lighted » Sun Jul 13, 2014 7:06 pm

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();
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10305 - Ordering Tasks

Post by uDebug » Thu Apr 16, 2015 1:06 pm

Replying to follow the thread.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Mohammad Erfan
New poster
Posts: 1
Joined: Tue May 26, 2015 9:03 am

Re: 10305 - Ordering Tasks

Post by Mohammad Erfan » Tue May 26, 2015 9:09 am

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

Post Reply

Return to “Volume 103 (10300-10399)”