ACM UVA-10305

單純的topological sort。

//ignore header files
int main(int argc, char const* argv[])
{
    int n,m;
    while(scanf("%d %d",&n,&m) && !(n == 0 && m == 0)){
        vector<int> G[105];
        int ref[105] = {0};
        while(m--){
            int a,b;
            scanf("%d %d",&a,&b);
            G[a].push_back(b);
            ref[b]++;
        }
        //topological sort
        queue<int> q;
        for(int i = 1;i <= n;i++){
            if(ref[i] == 0)
                q.push(i);
        }
        bool first = true;
        while(!q.empty()){
            int a = q.front();
            if(first){
                printf("%d",a);
                first = false;
            }
            else
                printf(" %d",a);
            q.pop();
            ref[a] = -1;
            for(size_t i = 0;i<G[a].size();i++){
                int b = G[a][i];
                ref[b]--;
                if(!ref[b]){
                    q.push(b);
                }
            }

        }
        puts("");
    }
    return 0;
}