70 lines
1.7 KiB
C++
70 lines
1.7 KiB
C++
#include <cstring>
|
|
#include <iostream>
|
|
#include <vector>
|
|
|
|
using namespace std;
|
|
|
|
class Graph {
|
|
public:
|
|
using VertexId = int;
|
|
using EdgeId = int;
|
|
|
|
struct Edge {
|
|
VertexId target_vertex = -1;
|
|
EdgeId next_edge = -1;
|
|
};
|
|
|
|
vector<Edge> edges;
|
|
vector<EdgeId> 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) {
|
|
// 如果从小到大 dfs，是不需要在此处取 max 的
|
|
if (ans_cache[vertex] != -1) { return ans_cache[vertex]; }
|
|
ans_cache[vertex] = vertex;
|
|
if (graph.first_edges[vertex] == -1) { return ans_cache[vertex]; }
|
|
for (int edge_id = graph.first_edges[vertex]; edge_id != -1; edge_id = graph.edges[edge_id].next_edge) {
|
|
ans_cache[vertex] = max(ans_cache[vertex], dfs(graph, graph.edges[edge_id].target_vertex));
|
|
}
|
|
return ans_cache[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(x - 1, y - 1);
|
|
}
|
|
|
|
memset(ans_cache, -1, sizeof(ans_cache));
|
|
|
|
for (int vertex = 0; vertex < v; vertex++) {
|
|
cout << dfs(graph, vertex) + 1 << " ";
|
|
}
|
|
cout << endl;
|
|
|
|
return 0;
|
|
}
|