#include #include #include using namespace std; class Graph { public: using VertexId = int; using EdgeId = int; struct Edge { VertexId target_vertex = -1; EdgeId next_edge = -1; }; vector edges; vector first_edges; explicit Graph(int vertices_amount, int edges_amount = 0) : first_edges(vertices_amount, -1) { edges.reserve(edges_amount); } void add_edge(VertexId source_vertex, VertexId target_vertex) { const EdgeId edge_id = edges.size(); edges.push_back({.target_vertex = target_vertex, .next_edge = first_edges[source_vertex]}); // 所以遍历顺序相反! first_edges[source_vertex] = edge_id; } }; constexpr int MAX_V = 1e5 + 5; int v, e; int ans_cache[MAX_V]; int dfs(const Graph& graph, int vertex, int start_vertex) { if (ans_cache[vertex] != -1) { return ans_cache[vertex]; } ans_cache[vertex] = start_vertex; for (int edge_id = graph.first_edges[vertex]; edge_id != -1; edge_id = graph.edges[edge_id].next_edge) { dfs(graph, graph.edges[edge_id].target_vertex, start_vertex); } return ans_cache[vertex]; } int dfs(const Graph& graph, int vertex) { // 反向建图,从大到小 dfs return dfs(graph, vertex, vertex); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> v >> e; Graph graph(v, e); for (int _ = 0; _ < e; _++) { int x, y; cin >> x >> y; graph.add_edge(y - 1, x - 1); // Reversed graph } memset(ans_cache, -1, sizeof(ans_cache)); for (int vertex = v - 1; vertex >= 0; vertex--) { dfs(graph, vertex); } for (int vertex = 0; vertex < v; vertex++) { cout << ans_cache[vertex] + 1 << " "; } cout << endl; return 0; }