Can anyone give some idea to minimise time?
- Code: Select all
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<sstream>
#include<vector>
#include<map>
#include<string>
using namespace std;
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define infile(a) freopen(a,"r",stdin)
#define diff(a,b) a>b? (a-b):(b-a)
#define MAXINT (int)(pow(2,31)-1)
#define inf pow(2,31)-1
#define ss 1000002
vector< vector < pair<int,int> > > G(ss);
//int G[ss][ss];
int visited[ss];
int V, E;
int i,j,k,u,v;
int list[ss],indegree[ss];
void init()
{
for(int i=0; i<ss; i++)
{
visited[i]=0;
indegree[i]=0;
G[i].clear();
}
}
void topsort()
{
// when G[a][b] = 1, that means a must come before b
// indegree[i] = number of items that that must come before i
// when taken[i] = 1, means we already have taken ith item
int invalid = 0,p,l,s;
for(i=0; i<V; i++)
{
for(j=0; j<V; j++)
if( !indegree[j] && !visited[j] )
{
visited[j] = 1;
list[i] = j+1;
// in this step we are taking item j
// we'd update the indegree[k] of items that depended on j
for(k=0; k<G[j].size(); k++)
{
p=G[j][k].first;
s= G[j][k].second;
if( !visited[s] && p )
--indegree[s];
}
break;
}
if( j == V )
{
invalid = 1;
break;
}
}
if( invalid )
printf("IMPOSSIBLE\n");
else
for(i=0; i<V; i++)
{
printf("%d\n", list[i] );
}
}
int main()
{
//freopen("10305.txt","r",stdin);
int m,n;
while(scanf("%d %d",&V,&E)==2)
{
if(V==0 && E==0)
break;
init();
for(i=0; i<E; i++)
{
scanf("%d %d",&u,&v);
//G[u-1][v-1]=1; // using 0 to n-1
G[u-1].push_back(make_pair(1,v-1));
indegree[v-1]++;
}
/* k=0;
if(E>0)
{
//finding the first node which has no predecessor defined.
for(i=0; i<V; i++)
{
if( (l[i]==1 && r[i]==0 ) )
break;
}
dfs(i);
}
else*/
topsort();
}
return 0;
}
Thanks in advanced.