B3644 【模板】拓扑排序 / 家谱树

//Kahn算法 o(n+m) 
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
vector<int> g[N];
int deg[N];
int n;void topo() {queue<int> q;for(int i=1; i <= n; i++) if(!deg[i]) q.push(i);while(!q.empty()) {int u=q.front(); cout << u << ' ';q.pop();for(auto v : g[u]) {deg[v]--; if(deg[v] == 0) q.push(v);}}
}int main() {cin >> n;for(int i=1, v; i <= n; i++) { while(cin >> v) {if(v == 0) break; g[i].push_back(v);deg[v]++; }} topo();return 0;
}

//dfs法 o(n+m) 正建图，倒序输出 
#include <bits/stdc++.h>
using namespace std;
const int N=105;
vector<int> g[N], a;
int vis[N];
void dfs(int u) {vis[u]=true;for(auto v : g[u]) if(!vis[v]) dfs(v);a.push_back(u);
}int main() {int n, m;cin >> n;for(int i=1, v; i <= n; i++) { while(cin >> v) {if(v == 0) break; g[i].push_back(v);}}for(int i=1; i <= n; i++) if(!vis[i]) dfs(i); reverse(a.begin(), a.end()); for(auto i : a) cout << i << ' ';return 0;
}

//dfs法 o(n+m) 反建图，正序输出 
#include <bits/stdc++.h>
using namespace std;
const int N=105;
vector<int> g[N], a;
int vis[N];
void dfs(int u) {vis[u]=true;for(auto v : g[u]) if(!vis[v]) dfs(v);a.push_back(u);
}int main() {int n, m;cin >> n;for(int i=1, v; i <= n; i++) { while(cin >> v) {if(v == 0) break; g[v].push_back(i); //反建图法 }}for(int i=1; i <= n; i++) if(!vis[i]) dfs(i); for(auto i : a) cout << i << ' ';return 0;
}