無ループ図のトポロジー的な順序付けが実現されています.
考え方:0に入る点から探し始め、見つけたらansに入れて、その点に隣接するすべての辺を取り除く.続けて2番目の0に入る点を探して、順番に類推します.
#include
#include
#include
#include
using namespace std;
const int MAX_V = 101;
int V, m;
vector<int> map[MAX_V];
int deg[MAX_V];
queue<int> ans;
void topo() {
queue<int> q;
for (int i = 1; i <= V; i++) {
if (!deg[i]) {
q.push(i);
}
}
while (q.size()) {
int tmp = q.front();
q.pop();
ans.push(tmp);
for (auto i : map[tmp]) {
deg[i]--;
if (!deg[i])
q.push(i);
}
}
}
int main() {
cin >> V >> m;
memset(deg, 0, sizeof(deg));
while (m--) {
int a, b;
cin >> a >> b;
map[a].push_back(b);
deg[b]++;
}
topo();
while (ans.size()) {
cout << ans.front() << " ";
ans.pop();
}
return 0;
}