10305 - Ordering Tasks

[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.....
[/b]

[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.

[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??

[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.

[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]

[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.

[miras]

don.t use BREAk

[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 ??

[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???

[miras]

ello ther is no problem but i still got WA i don.y know what is wrong hear;



BTW theanks;

end;
end.
MIRAS

[Noim]

Mr. Miras,

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

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

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

[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...

[mido]

Stupid error that I found...duh

[Algoritmo]

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

[mido]

None of those, believe it or not...it's the kind of error that makes you bang your head against the wall....