Lien Conceptuel entre les Structures
L'arbre de reconstruction de Kruskal et l'arbre cartésien partagent des propriétés structurelles fondamenatles. L'arbre de reconstruction de Kruskal est particulièrement efficace pour résoudre les problèmes de connectivité avec des contraintes de valeurs minimales ou maximales sur les arêtes d'un graphe ou d'un arbre.
Construction de l'Arbre de Reconstruction de Kruskal
La méthode de construction repose sur l'algorithme de Kruskal. Lors de la fusion de deux composantes connexes via une arête, un nouveau nœud est créé. Les racines des deux composantes connexes deviennent les enfants de ce nouveau nœud, et le poids de ce nouveau nœud est défini par le poids de l'arête utilisée pour la fution.
Propriétés Fondamentales
En supposant que l'arbre est construit pour un arbre couvrant minimal (les arêtes sont triées par poids croissant) :
- Les poids des nœuds augmentent à mesure que l'on se rapproche de la racine.
- Le poids maximal sur le chemin entre deux nœuds dans le graphe original correspond exactement au poids de leur plus petit ancêtre commun (LCA) dans l'arbre de reconstruction.
- Étant donné un nœud de départ et une contrainte de poids maximal sur les arêtes, tous les nœuds accessibles se trouvent dans la sous-arbre du plus proche ancêtre dont le poids satisfait la contrainte.
Contrairement à l'algorithme de Kruskal satndard qui ne conserve que les arêtes finales, l'arbre de reconstruction préserve la morphologie de l'arbre et les états intermédiaires. Grâce à sa propriété de tas, il permet de gérer dynamiquement différentes contraintes de valeurs.
Résolution de Requêtes avec Contraintes
Pour déterminer la racine de la sous-arbre accessible depuis un nœud donné avec une limite de poids, on utilise la technique des sauts binaires (binary lifting). En décomposant la recherche par puissances de deux, on peut remonter l'arbre efficacement.
Gestion des Requêtes en Ligne : K-ième Plus Grand Élément
Pour les problèmes nécessitant de trouver le k-ième plus grand poids de nœud dans une sous-arbre accessible (avec des requêtes forcées en ligne), la structure de l'arbre doit être linéarisée. En utilisant l'ordre de parcours en profondeur (DFS order), le problème de la sous-arbre est transformé en un problème de requête sur un intervalle continu. Un arbre de segments persistant (persistent segment tree) est ensuite utilisé pour répondre aux requêtes du k-ième élément dans cet intervalle.
Implémentation C++ : Requêtes de Connectivité avec Contraintes
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 200010;
const int MAX_LOG = 18;
struct Edge {
int u, v, w;
bool operator<(const Edge& other) const {
return w < other.w;
}
};
struct PersistentSegTree {
int lc[MAX_N * 20], rc[MAX_N * 20], sum[MAX_N * 20];
int roots[MAX_N], tot;
int insert(int pre, int l, int r, int pos) {
int p = ++tot;
lc[p] = lc[pre]; rc[p] = rc[pre]; sum[p] = sum[pre] + 1;
if (l == r) return p;
int mid = (l + r) >> 1;
if (pos <= mid) lc[p] = insert(lc[pre], l, mid, pos);
else rc[p] = insert(rc[pre], mid + 1, r, pos);
return p;
}
int query(int pre, int p, int l, int r, int k) {
if (l == r) return l;
int mid = (l + r) >> 1;
int right_sum = sum[rc[p]] - sum[rc[pre]];
if (k <= right_sum) return query(rc[pre], rc[p], mid + 1, r, k);
return query(lc[pre], lc[p], l, mid, k - right_sum);
}
} seg;
vector<int> adj[MAX_N];
vector<Edge> edges;
int up[MAX_N][MAX_LOG];
int node_val[MAX_N];
int in_time[MAX_N], out_time[MAX_N], timer_dfs;
int dfs_seq[MAX_N], original_weights[MAX_N], sorted_weights[MAX_N];
bool is_internal[MAX_N];
int total_nodes, num_vertices;
struct DSU {
int parent[MAX_N];
void init(int n) { for (int i = 1; i <= n; ++i) parent[i] = i; }
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
} dsu;
void dfs(int u) {
in_time[u] = ++timer_dfs;
if (u <= num_vertices) dfs_seq[timer_dfs] = original_weights[u];
for (int v : adj[u]) dfs(v);
out_time[u] = timer_dfs;
}
void build_tree() {
total_nodes = num_vertices;
dsu.init(num_vertices * 2);
sort(edges.begin(), edges.end());
for (const auto& e : edges) {
int r1 = dsu.find(e.u), r2 = dsu.find(e.v);
if (r1 == r2) continue;
++total_nodes;
node_val[total_nodes] = e.w;
up[r1][0] = up[r2][0] = total_nodes;
adj[total_nodes].push_back(r1);
adj[total_nodes].push_back(r2);
dsu.parent[r1] = dsu.parent[r2] = total_nodes;
is_internal[r1] = is_internal[r2] = true;
}
for (int j = 1; j < MAX_LOG; ++j)
for (int i = 1; i <= total_nodes; ++i)
up[i][j] = up[up[i][j - 1]][j - 1];
}
void build_seg_tree() {
for (int i = 1; i <= total_nodes; ++i) {
if (!is_internal[i]) dfs(i);
}
for (int i = 1; i <= num_vertices; ++i) {
seg.roots[i] = seg.insert(seg.roots[i - 1], 1, num_vertices, dfs_seq[i]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int num_edges, num_queries;
cin >> num_vertices >> num_edges >> num_queries;
for (int i = 1; i <= num_vertices; ++i) {
cin >> original_weights[i];
sorted_weights[i] = original_weights[i];
}
sort(sorted_weights + 1, sorted_weights + num_vertices + 1);
int unique_cnt = unique(sorted_weights + 1, sorted_weights + num_vertices + 1) - sorted_weights - 1;
for (int i = 1; i <= num_vertices; ++i) {
original_weights[i] = lower_bound(sorted_weights + 1, sorted_weights + unique_cnt + 1, original_weights[i]) - sorted_weights;
}
for (int i = 0; i < num_edges; ++i) {
int u, v, w;
cin >> u >> v >> w;
edges.push_back({u, v, w});
}
build_tree();
build_seg_tree();
while (num_queries--) {
int u, limit, k;
cin >> u >> limit >> k;
for (int i = MAX_LOG - 1; i >= 0; --i) {
if (up[u][i] && node_val[up[u][i]] <= limit) {
u = up[u][i];
}
}
int res = seg.query(seg.roots[in_time[u] - 1], seg.roots[out_time[u]], 1, num_vertices, k);
if (res == 0) cout << -1 << "\n";
else cout << sorted_weights[res] << "\n";
}
return 0;
}
Implémentation C++ : Plus Courts Chemins avec Contraintes
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX_N = 400010;
const int MAX_LOG = 20;
const long long INF = 1e18;
struct GraphEdge {
int to, nxt;
long long w;
};
struct KruskalEdge {
int u, v;
long long w;
bool operator<(const KruskalEdge& other) const {
return w < other.w;
}
};
vector<GraphEdge> graph;
int head[MAX_N], edge_cnt;
vector<int> tree_adj[MAX_N];
int up[MAX_N][MAX_LOG];
long long edge_val[MAX_N];
long long min_dist[MAX_N];
int dsu_parent[MAX_N];
int total_nodes, num_vertices;
void add_edge(int u, int v, long long w) {
graph.push_back({v, head[u], w});
head[u] = graph.size() - 1;
}
void dijkstra() {
vector<long long> dist(num_vertices + 1, INF);
vector<bool> vis(num_vertices + 1, false);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
dist[1] = 0;
pq.push({0, 1});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (int i = head[u]; i != -1; i = graph[i].nxt) {
int v = graph[i].to;
long long w = graph[i].w;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
for (int i = 1; i <= num_vertices; ++i) min_dist[i] = dist[i];
}
int find(int x) {
return dsu_parent[x] == x ? x : dsu_parent[x] = find(dsu_parent[x]);
}
void dfs(int u) {
if (u <= num_vertices) return;
min_dist[u] = INF;
for (int v : tree_adj[u]) {
dfs(v);
min_dist[u] = min(min_dist[u], min_dist[v]);
}
}
void build_kruskal_tree(vector<KruskalEdge>& edges) {
total_nodes = num_vertices;
for (int i = 1; i <= num_vertices * 2; ++i) dsu_parent[i] = i;
sort(edges.begin(), edges.end());
for (const auto& e : edges) {
int r1 = find(e.u), r2 = find(e.v);
if (r1 == r2) continue;
++total_nodes;
edge_val[total_nodes] = e.w;
up[r1][0] = up[r2][0] = total_nodes;
tree_adj[total_nodes].push_back(r1);
tree_adj[total_nodes].push_back(r2);
dsu_parent[r1] = dsu_parent[r2] = total_nodes;
}
dfs(total_nodes);
for (int j = 1; j < MAX_LOG; ++j)
for (int i = 1; i <= total_nodes; ++i)
up[i][j] = up[up[i][j - 1]][j - 1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int num_edges1, num_edges2, K, S;
long long last_ans = 0;
cin >> num_vertices >> num_edges1;
fill(head + 1, head + num_vertices + 1, -1);
graph.clear();
for (int i = 1; i <= total_nodes; ++i) tree_adj[i].clear();
vector<KruskalEdge> k_edges;
for (int i = 0; i < num_edges1; ++i) {
int u, v;
long long w1, w2;
cin >> u >> v >> w1 >> w2;
add_edge(u, v, w1);
add_edge(v, u, w1);
k_edges.push_back({u, v, w2});
}
dijkstra();
build_kruskal_tree(k_edges);
cin >> num_edges2 >> K >> S;
while (num_edges2--) {
long long v_enc, p_enc;
cin >> v_enc >> p_enc;
int v = (v_enc + K * last_ans - 1) % num_vertices + 1;
long long p = (p_enc + K * last_ans) % (S + 1);
int curr = v;
for (int i = MAX_LOG - 1; i >= 0; --i) {
if (up[curr][i] && edge_val[up[curr][i]] <= p) {
curr = up[curr][i];
}
}
last_ans = min_dist[curr];
cout << last_ans << "\n";
}
}
return 0;
}
Connexion avec l'Arbre Cartésien
L'arbre de reconstruction de Kruskal peut être conceptualisé comme un arbre cartésien construit sur les arêtes du graphe. Tout comme l'arbre cartésien organise un tableau en respectant une propriété de tas sur les valeurs et une propriété d'arbre binaire de recherche sur les indices, l'arbre de reconstruction de Kruskal organise les fusions de composantes connexes en respectant une propriété de tas sur les poids des arêtes. Cette dualité structurelle explique pourquoi les deux arbres partagent des comportements algorithmiques similaires lors de la résolution de problèmes d'optimisation sous contraintes.