10305 - Ordering Tasks

[asif_rahman0]

thnx darko. i did wrong method.
now i changed my method & follow --"i must be executed before task j"!!!

so!!!!:(

more I/O.

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

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

5 4
1 2
2 3
1 3
1 5
output:
1 4 2 3 5

so correct??

[Darko]

Your output looks OK to me, what method are you using?

Btw, for that input

Code: Select all

12 7 
1 3 
3 8 
3 4 
4 12 
4 7 
7 11 
7 10
12 10 
1 3 
3 8 
3 4 
8 12 
4 7 
7 11 
7 10 
3 2 
4 5 
12 9
5 4 
1 2 
2 3 
1 3 
1 5
0 0

I got this:

Code: Select all

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

[asif_rahman0]

i just used DFS.
sorry for being late reply.
here is my code. plz help me to get accepted.

Code: Select all

code removed

[asif_rahman0]

plz reply me anybody.

[Darko]

Why do you start your dfs from 1?

Try this:

Code: Select all

3 3
2 1
2 3
3 1
0 0

[asif_rahman0]

thnx Mr. darko

[Shuvra(CSE-BUET)]

I don't know why this type of normal topological sort gives me WA after .002 secs for 5 times. If the algo is right there is not even any necessity to check several inputs. But I tried all the inputs posted before but could not find out the bug.
Now plssssssssssssss check my code and help me.
........................................................................................................
code deleted after ACC
Thanks DP.It was an initialization error.

[DP]

Advice:
There is already some post ... so i think you should better to use those.

Now your program is OK. But there is initialization error.
Because i try several I/O again and again then it produces first correct output then wrong output.

Hope its help.

[rahul]

plz help me , im getting RA .can u plz tell me where im wrong.
im posting my code ..

Code: Select all

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class acm
{
 public:
  int xxx()
  {         
	          vector< vector<int> > a;
              int n1,n2,first=0,last=0,co=0,count=0,count1=0,co1=0;
              vector<int> v,ans;
  	          cin>>n1>>n2;
	          while(n1!=0 || n2!=0)
	          {
		      v.push_back(n1);
		      v.push_back(n2);
		      a.push_back(v);
		      v.clear();
		      cin>>n1>>n2;
              }
	       for(int i=1;i<=a[0][1];i++)
	       {  
                   for(int j=1;j<=a[0][1];j++)
                    {
                     if(a[i][0]==a[j][1])
                      count++;    
                    }
            if(count==0)
             {
             ans.push_back(a[i][0]);
             
             break;
              } 
            }  
            for(int j=1;j<=a[0][1];j++)
            {
                
                              
              for(int i=0;i<ans.size();i++)
               {
                     if(a[j][0]==ans[i] )
                     first=1;
                     if(a[j][1]==ans[i])
                     last=1;                 
               } 
                     if(first!=1 && last!=1)
                     {
                                 ans.push_back(a[j][0]);
                                 ans.push_back(a[j][1]);
                                 first=0;
                                 last=0;
                     }
                     if(first==1 && last !=1)
                     {
                                 ans.push_back(a[j][1]);
                                 first=0;
                                 last=0;
                          
                     }
                     if(first!=1 && last==1)
                     {
                        for(int tt=0;tt<ans.size();tt++)
                        {
                                if(a[j][1]==ans[tt])
                                co1++;
                                break;
                        }
                        ans.insert(ans.begin()+co1,a[j][0]);
                                 
                     }
                     if(first==1 && last ==1)
                     {
                                  first=0;
                                   last=0;
                                     co=0;
                                       for(int k=0;k<ans.size();k++)
                                        {
                                            if(ans[k]!=a[j][1])
                                            {
                                                    co++;
                                            } 
                                            if(ans[k]==a[j][1])
                                            break;  
                                        }  
                                         for(int t=0;t<co;t++)
                                         {
                                                  if(ans[t]==a[j][0])
                                                   {
                                                          count1=1;               
                                                   }
                                         }
                                          if(count1!=1)
                                          {
                                              for(int r=0;r<ans.size();r++)
                                               {
                                                     if(ans[r]==a[j][0])
                                                     {
                                                        ans.erase(ans.begin()+r);
                                                        ans.insert(ans.begin()+co,a[j][0]); 
                                                        break;              
                                                      }  
                                                }      
                                          }       
                               
                     }
                    
            }	
     for(int i=1;i<=a[0][0];i++)
     {
       for(int j=0;j<ans.size();j++)
       {
           if(i==ans[j])
           co++;   
       } 
       if(co==0)
       {
            ans.push_back(i); 
       }  
       else
       co=0;
     }
     for(int i=0;i<ans.size();i++)
     {
          cout<<ans[i]<<" ";
     }
     return 0; 
 }
};
int main()
{
    class acm x;
    x.xxx();
}

[williamban]

Hi, noob's passing by. I tried this problem but I got a WA during 0.000 seconds. I have checked my program with the input above, and I find them logically correct. I do not know what's wrong, so I hope you guys can give me any hints on what I have done wrong.

Btw, I'm using a basic algorithm of in-degree counting.

Code: Select all

Code Removed.

The following are the inputs and their respective outputs:

Code: Select all

12 7
1 3
3 8
3 4
4 12
4 7
7 11
7 10

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

12 10
1 3
3 8
3 4
8 12
4 7
7 11
7 10
3 2
4 5
12 9

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

5 4
1 2
2 3
1 3
1 5

Output: 1 4 2 5 3

Thanks in advance.

[williamban]

Sorry. I have found the error. My program fails when the number of links is 0. For example, inputs like 5 0.

Thanks anyway.

[bishop]

ok code results everything okay
but WA why

Code: Select all

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define S 222
#define INF 9999
vector<int> adj[S];
enum{White=0, Gray, Black,NO};
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,less<PII> > P;
int color[S];
int A[S];
int pre[S];
int d[S];
int F[S];
int N,M,tme;
void initialize()
{
	int i,j;
	for(i=0; i<S; i++)
	{
		F[i]=0; pre[i]=-1;d[i]=INF;
		adj[i].clear();color[i]=NO;
		for(j=0; j<S; j++){}
	}
}
void DFS(int u)
{
	color[u]=Gray;
	tme++;
	d[u]=tme;
	for(int i=0; i< adj[u].size(); i++)
	{
		int v=adj[u][i];
		if(color[v]==White)
		{
			pre[v]=u;		
			DFS(v);
		}
	}

	color[u]=Black;
	tme=tme+1;
	F[u]=tme;
}

int main()
{
	int u,v,s,t;
	int i,j,k,l;
	while(scanf("%d%d",&N,&M)==2&&N&&M)
	{
		initialize();
		for(i=0; i<M; i++)
		{
			scanf("%d%d",&u,&v);
			adj[u].push_back(v);
			color[u]=color[v]=White;
		}
		tme=0;
		for(i=1; i<=N; i++)
		{
			if(color[i]==White)
			{
				DFS(i);
			}
		}
		//cout << "Node\tDiscovery\tfinishing\n";
		for(i=1; i<=N; i++)
		{
			//cout << i<<"\t"<<d[i]<<"\t\t"<<F[i]<<endl;
			P.push(make_pair(F[i],i));
		}

		while(!P.empty())
		{
			int n=P.top().second;
			int f=P.top().first;
			P.pop();
			cout << n<<" ";//<<f<<endl;
		}
		cout << endl;
	}

	return 0;
}

[vahid sanei]

it`s really strange , for this problem we should use topological sort and dfs but i get Acc with this code

Code: Select all

struct d{
	int x;double t;
}list[101];
int main(){
	//ifstream cin("c.in");
	int n,m;
	while(cin>>n>>m&&!(!n&&!m)){
		int x,y;
		for(int i=0;i<=n;i++)	list[i].x=i,list[i].t=0;
		for(int i=0;i<m;i++)		cin>>x>>y,list[x].t-=1.0,list[y].t+=1.5;
		for(int i=1;i<=n;i++){// sorting
			for(int j=i+1;j<=n;j++){
				if(list[i].t>list[j].t){
					swap(list[i].t,list[j].t);
					swap(list[i].x,list[j].x);
				}
			}
		}
		for(int i=1;i<n;i++)	cout<<list[i].x<<" ";
		cout<<list[n].x<<endl;
	}
}

please anybody reply me why I get acc ,
i think this method is wrong ,(maybe inputs aren`t challengeable)
do u agree with me ???

[Yuna Reichmann]

i get RE error each time i submit

please anyone tell me what might the reason be?

any help would be appreciated..

Code: Select all

removed after AC

[Khaled91]

hi,,,
what wrong with this
gave me run time error every time i submit it
help,,


#include<iostream>
#include<vector>
#include<queue>
using namespace std;
void logic (vector<vector <int> > graph)
{
vector<int> ret;
vector<int> indgree(graph.size(),0);
queue<int> q;
for(int i=0;i<graph.size();i++)
for(int j=0;j<graph.size();i++)
indgree[graph[j]] ++;
for(int i=0;i<graph.size();i++)
if(!indgree) q.push(i);
while(! q.empty())
{
int res=q.front();
q.pop();
ret.push_back(res);
for(int i=0;i<graph[res].size();i++)
{
indgree[graph[res]]--;
if(! indgree[graph[res]]) q.push(graph[res]);
}

}
if(ret.size()!=graph.size())
ret.clear();
for(int i=1;i<graph.size();i++)
cout<<ret<<" ";
}
int main()
{
//freopen("in.txt","rt",stdin);
//freopen("out.txt","wt",stdout);
int n,m;
cin>>n>>m;
int nn=n;
vector<int> res(n);
vector<vector <int> > graph(n+1);
while(nn>0)
{
cin>>n>>m;
if(n==0&&m==0) break;
graph[n].push_back(m);
nn--;
}
logic(graph);
return 0;
}