11686 - Pick up sticks

[arifcsecu]

removed

[saiful_sust]

Thanks arifcsecu.......
ur too much helpful........

keep posting ......
Another thing PLz remove ur post ....

[Bruno]

I am getting WA, anybody could give me another sample input (one that may fail)?

I tried this:

Code: Select all

4 3
4 1
1 2
3 2
3 2
1 2
2 3
4 4
2 1
3 2
4 3
2 4
0 0

And output is:

Code: Select all

4
1
3
2
1
2
3
IMPOSSIBLE

Just like the toolkit

[Bruno]

Got accepted, I was forgetting to clear the vectors

Anyway, I needed to change from cin to scanf! With cin I got TLE! This should be considered by the judges as cin/scanf should not interfere in the algorithm complexity and performance Should it???

[arifcsecu]

Read previous post

[Bruno]

Read previous post

Which one?

[arifcsecu]

Cin and cout take more time than scanf and printf

[serur]

Now I see how that color stunt is helpful in dfs. In the sample input above one edge is given twice, so it is easy to mistake it for a cycle during dfs, if one doesn't use colors.

[arifcsecu]

Exactly correct.
Back edge can easily be detected using color arrary

[Rashad]

I am getting WA. Give me some test case. Thanks in advance.

[sohel]

You can test your code with your own test cases using this site: http://uvatoolkit.com/problemssolve.php

[Rashad]

I tried that. But I was getting WA. Now I got AC. I was making some silly mistakes in initialization. Thanks a lot.

[ujjal.ruet]

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.

[Scarecrow]

can't find the bug in my code. plz help someone..

Code: Select all

AC :D
be sure to clear the vectors before each test case. i got WA for this reason

[MauriWilde]

I can't figure out why I'm getting WA :/ could you help me?

My code (c++):

Code: Select all

 Removed after AC

Thank you in advance ^-^

UPD: I was checking cycles existence wrong.