(UVA) 11686 - Pick up sticks

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2733

主要是topological sort啦。比較需要注意的是N比較大(10^6)，要小心不要co爛掉。

#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;

const int MAX_N = 1e6 + 3;

int rudu[MAX_N];
vector<int> edg[MAX_N];
queue<int> que;
bool visit[MAX_N];
int ans[MAX_N];

int main (){
    int n,m;
    while (scanf("%d %d",&n,&m) != EOF) {
        if (!n && !m) break;
        for(int x=0;n>=x;x++) {
            edg[x].clear();
            rudu[x]=0;
            visit[x]=false;
        }
        for (int x=0;m>x;x++) {
            int i,j;
            scanf("%d %d",&i,&j);
            edg[i].push_back(j);
            rudu[j]++;
        }
        int id=0;
        for (int x=1;n>=x;x++) {
            if (rudu[x]==0 && visit[x]==false) {
                que.push(x);
                while (!que.empty()) {
                    int t=que.front();
                    ans[id++]=t;
                    visit[t]=true;
                    que.pop();
                    for (auto i=edg[t].begin();i!=edg[t].end();i++) {
                        int tmp=*i;
                        rudu[tmp]--;
                        if (rudu[tmp]==0) que.push(tmp);
                    }
                }
            }
        }
        if (id!=n) puts("IMPOSSIBLE");
        else {
            for(int x=0;id>x;x++) {
                printf("%d\n",ans[x]);
            }
        }
    }
}