Page 1 of 4

10305 - Ordering Tasks

Posted: Mon Mar 17, 2003 8:45 am
by anupam
first please check,,

Code: Select all

cut it off please don't mind..
it's a sol after some reply...
thanks to tomal bhai...
this is a simple code of topological sorting,,
but i get wa for several times..
i can't understand why?

then i tried a very easy algirithm..
just compute the in degree of graph nodes but again wa..
am i missing something??
please please help...
i have no way left..

the second code... is pasted here....
please don't mind, i pasted it after at least 10 trials..and getting wa....

Code: Select all

#include<stdio.h>
#define N 100
main()
{
	freopen("in.txt","r",stdin);
	int m,n,b[N],out[N],i,j,c,d,h,e[N],f[N],high,l,k,r[N],pr;
	while(1)
	{
		scanf("%d%d",&n,&m);
		pr=0;
		if(m==0 && n==0) break;
		for(i=0;i<n;i++) b[i]=out[i]=0,r[i]=i;
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&c,&d);
			b[c-1]++;out[d-1]++;
		}
		for(i=0;i<n-1;i++)
		{
			h=i;
			for(j=i+1;j<n;j++)
				if(b[j]>b[h]) h=j;
			c=b[h];
			d=out[h];
			b[h]=b[i];
			out[h]=out[i];
			out[i]=d;
			b[i]=c;
			c=r[i];
			r[i]=r[h];
			r[h]=c;
		}
		high=0;
		for(i=0;i<n;i++) if(b[i]>high) high=b[i];
		for(;high>=0;high--)
		{
			l=0;
			for(j=0;j<n;j++) if(b[j]==high) e[l]=j,f[l++]=out[j];
			for(j=0;j<l-1;j++)
			{
				h=j;
				for(k=j+1;k<l;k++)
					if(out[e[k]]<out[e[h]]) h=k;
				k=e[j];
				e[j]=e[h];
				e[h]=k;
			}
			for(i=0;i<l;i++)
			{
				if(pr) printf(" ");
				else pr=1;
				printf("%d",e[i]+1);
			}
		}
		printf("\n");
	}
	return 0;
}
if any one helps me i will be greatfull.
pleases ...
thanks.....
:oops: :oops: :oops: :oops: :oops: :oops: :oops: :oops: :oops: [/b]

Posted: Mon Mar 17, 2003 4:48 pm
by kmhasan
The code for topological sorting should work. I did it almost the same way. The part which I get a bit confused is where you swap the elements of array a. It seems like your doing some sort of Selection Sort there. I'm not sure if that is correct.

If you had kept the nodes in a global stack when you do the DFS, then you could simply pop and print them after the DFS is done.

[cpp]
void dfs(int u)
{
int i;
time++;
c='g';
for(i=0;i<n;i++)
if(c=='w' && b==1)
dfs(i);
S[top++] = u; /* this is what I suggest */
}
[/cpp]

I hope it might help.

Posted: Tue Mar 18, 2003 6:12 am
by anupam
if i get the finishing time the sorting represent the finishing time..
as the stack represent..
is there any error(bhul) in my code without using the stack..
tomal bhai apni boss..
apnar ebarer help 100% kaj diyeche...
but i can't understand why coreman is wrong or i am wrong in this case...
ektu explain korben??
:P :P

10305 - ordering tasks

Posted: Fri Apr 25, 2003 5:54 pm
by jura
Do I have a wrong approach or what?
I dunno why i get WA.


program tasks;
var level:array[1..100] of byte;
nodes:array[1..6000,1..2] of byte;
m,n,i,j:integer;
gotovo,prva:boolean;

begin
while true do
begin
readln(n,m);
if (n=0) and (m=0) then halt;

for i:=1 to m do readln(nodes[i,1],nodes[i,2]);
fillchar(level,sizeof(level),1);
for i:=1 to n do
begin
gotovo:=true;
for j:=1 to m do
begin
if level[nodes[j,1]]=i then
begin
level[nodes[j,2]]:=i+1;
gotovo:=false;
end;
end;
if gotovo then break;
end;
prva:=true;
for i:=1 to n do
begin
gotovo:=true;
for j:=1 to n do
begin
if level[j]=i then
begin
if prva then
begin
write(j);
prva:=false;
end else write(' ',j);
gotovo:=false;
end;
end;
if gotovo then break;
end;
end;
end.

10305 WA why?

Posted: Sat Jul 12, 2003 3:33 pm
by boatfish
I just use topological sort, but keep on WA, why??

[cpp]
#include<iostream>
#include<queue>
#include<memory.h>
#include<algorithm>
using namespace std;

struct src{
int no;
int f;
};

bool graph[101][101];
int pre[101],color[101],t;
src f_c[101];

void DFS_VISIT(int u,int n){
int j;
color=2;
for(j=1;j<=n;j++){
if(graph[j] && color[j]==1){
pre[j]=u;
DFS_VISIT(j,n);
}
}
color=3;
t++;
(f_c).f=t;
}

void DFS(int n){
int i;
memset(pre,-1,101);
memset(color,1,101);
t=0;
for(i=1;i<=n;i++)
if(color==1)
DFS_VISIT(i,n);
}

bool new_less(src a,src b){
return a.f<b.f;
}

void print_path(int n){
sort(f_c,f_c+n,new_less);
for(int i=1;i<=n;i++)
cout<<(f_c).no<<' ';
}

int main(){
int n,m,a,b,i;
for(i=1;i<=100;i++)
(f_c).no=i;

while(cin>>n>>m,n){
memset(graph,1,10201);
for(i=1;i<=m;i++){
cin>>a>>b;
graph[a]=false;
}
DFS(n);
print_path(n);
cout<<endl;
}
return 0;
}[/cpp][/cpp]

Posted: Tue Jul 15, 2003 5:05 pm
by Noim
strange.

have you test your program for some input? your program does not work for many input.
it just prints the same output for all input.

Posted: Tue Sep 09, 2003 3:24 pm
by miras
don.t use BREAk
:D

10305

Posted: Tue Sep 09, 2003 3:26 pm
by miras
Elo if input is
5 4
1 2
2 3
1 3
1 5
0 0


can the noutput be
1 2 3 5 4 ?? :D

Posted: Sat Sep 13, 2003 7:39 pm
by Noim
yes the output would be: 1 2 3 5 4
what's the reason you have menteioned that?
is there any problem??? or any disagree???

Posted: Wed Sep 17, 2003 12:20 pm
by miras
ello ther is no problem but i still got WA i don.y know what is wrong hear;



BTW theanks;

end;
end.
MIRAS :lol:

Posted: Wed Sep 17, 2003 7:23 pm
by Noim
Mr. Miras,

i have not helped you yet. so why did you thank me , sir??? :wink:

ok you can try for the input below ( this is made by one of my freinds who got AC though his program output wrong for this input .....hahaha...)

input:
5 2
3 2
5 3
output can be one of many :lol:

ok , i can ensure you it is very easy problem and there is no meaningless critical input for this problem. you have to just implement a TOPOLOGICAL sort algorithm which can be found from any of the books of algorithm. may be thissss time, you can solve it . please inform here if you manage to solve this problem.
bye

Posted: Sun Sep 28, 2003 6:33 pm
by mido
Why does this go capoot(WA) :
[cpp]
#include <iostream.h>

long i,e,v,dep[105],x,y,j;
bool used[105],mat[105][105],first,vis[105];

void check(int x)
{
vis[x]=true;
int i;
if (dep[x]>0)
for (i=1;i<=v;i++)
{
if (mat[x] && !used && !vis[x]) check(i);
}

cout<<x<<" ";
used[x]=true;
vis[x]=false;
}

void main()
{
while (cin>>v>>e && (v||e))
{
for (i=1;i<=v;i++)
{
dep=0;
for (j=1;j<=v;j++)
mat[j]=false;
}
while (e--)
{
cin>>x>>y;
dep[y]++;

mat[y][x]=true;
}

for (i=1;i<=v;i++)
{
used=vis=false;
}

for (i=1;i<=v;i++)
{
if (dep==0) {cout<<i<<" ";used=true;}
}

cout.flush();

for (i=1;i<=v;i++)
{
if (dep>0 && !used) {check(i);}
}

cout<<char(8);

cout.flush();
cout<<endl;
}
}
[/cpp]
Thanks...

Posted: Thu Oct 02, 2003 7:21 pm
by mido
Stupid error that I found...duh

Posted: Tue Nov 25, 2003 8:23 am
by Algoritmo
mido wrote:Stupid error that I found...duh
Can I make sujestions ?

-=> You probably have noted that you should repeatedly print and check, not just print all then check all and quit. dep[] array is not beeing never decremented and I think you don't need so many arrays.
-=> In c++ we normally count from 0 to N-1 instead than from 1 to N. If you have an array of 105, they are numbered from 0 to 104.
-=> FORs with a single command dont need the brackets {}
-=> You dont need cout.flush() unless for test reasons maybe

Posted: Tue Nov 25, 2003 4:18 pm
by mido
None of those, believe it or not...it's the kind of error that makes you bang your head against the wall....:)