AOJ

# # Problem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B

# # Solution

With BFS

void tsort(vector<Int> edges[], Int n, vector<Int> &indeg, vector<Int> &result) {
vector<bool> done(n, false);
queue<Int> Q;

Int index = 0;
loop(i,0,n) {
if (indeg[i] > 0 || done[i]) continue;
Q.push(i);
done[i] = i;
result[index++] = i;

while (!Q.empty()) {
Int u = Q.front(); Q.pop();
for (Int v: edges[u]) {
indeg[v]--;
if (indeg[v] > 0 || done[v]) continue;
Q.push(v);
done[v] = true;
result[index++] = v;
}
}
}
}

int main(void) {
Int n, e, u, v;
cin >> n >> e;
vector<Int> edges[n];
vector<Int> indeg(n, 0);
loop(i,0,e) {
cin >> u >> v;
edges[u].push_back(v);
indeg[v]++;
}

vector<Int> result(n, 0);
tsort(edges, n, indeg, result);
loop(i,0,n) cout << result[i] << ' ';
cout << endl;
return 0;
}

Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!