11686 TLE

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

Moderator: Board moderators

11686 TLE

Postby ujjal.ruet » Thu Jan 26, 2012 1:34 pm

Getting tle.
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.
ujjal.ruet
New poster
 
Posts: 15
Joined: Thu Sep 02, 2010 3:10 pm
Location: Dhaka,Bangladesh

Return to Volume CXIX

Who is online

Users browsing this forum: No registered users and 2 guests