My solution of UVA 10305 Ordering Tasks

10305 - Ordering Tasks


Trace the graph with given edges direction.
- repeatly count all node in-degree, find the local root (in-degree=0), print it and remove its in-edge(in-arrow).


#include <iostream>
#include <sstream>


#include <algorithm>
#include <vector>
#include <list>


#define sz(k) (int)(k).size()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define forr(i,r) for(int i=0;i<r;i++)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define drep(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back


#define nl(c) c<<endl;
#define db(cout,c) tr(c,it){cout<<" "<<*it;};nl(cout); 
#define inf32 (int)(1<<31-1)
#define inf64 (int)(1<<63-1)


using namespace std;


int main(int argc, char *argv[])
{
    int N,M;


    while(cin>>N>>M)
    {
        if(N==0)break;
        long A[M],B[M];
        forr(i,M)
            cin>>A[i]>>B[i];
        long cnt=0;
        bool P[N+1];
        rep(i,0,N){P[i]=false;}
        while(true)
        {
            long C[N+1];
            rep(i,0,N){C[i]=0;}
            forr(i,M)
                if(B[i]>0)
                    C[B[i]]++;
            
            rep(i,1,N)
            if(!P[i])
            if(C[i]==0){
                forr(j,M)if(A[j]==i)B[j]=-1;
                cout<<i<<" ";
                P[i]=true;
                cnt++;
            };
            
            if(cnt>=N)break;
        }    
        cout<<endl;
/*        vector< pair<long,long> > T;
        forr(i,M){
            pair< long,long> pp;
            cin>>pp.second>>pp.first;
            T.push_back(pp);
        }
        sort(T.begin(),T.end());
        tr(T,ti)cout<<(*ti).first<<endl;
 */       
        
    }
    return 0;
}