File size: 4,215 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | #include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <random>
#include <chrono>
void solve() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, m;
std::cin >> n >> m;
// Scoring parameters are not used in the logic.
std::vector<int> a(10);
for (int i = 0; i < 10; ++i) {
std::cin >> a[i];
}
std::vector<std::vector<int>> adj(n + 1);
std::vector<int> out_degree(n + 1, 0);
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
out_degree[u]++;
}
// Sort adjacency lists by neighbor's out-degree in descending order.
// This pre-computation speeds up the greedy choice in each step.
for (int i = 1; i <= n; ++i) {
std::sort(adj[i].begin(), adj[i].end(), [&](int u, int v) {
return out_degree[u] > out_degree[v];
});
}
std::vector<int> best_path;
// Generate a random permutation of vertices to use as starting nodes.
std::vector<int> start_nodes(n);
std::iota(start_nodes.begin(), start_nodes.end(), 1);
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
std::shuffle(start_nodes.begin(), start_nodes.end(), rng);
// Use a marker technique for efficient 'visited' checks across multiple runs.
std::vector<int> visited_marker(n + 1, 0);
int run_id = 0;
auto start_time = std::chrono::steady_clock::now();
for (int start_node : start_nodes) {
// Stop if we approach the time limit.
auto current_time = std::chrono::steady_clock::now();
if (std::chrono::duration_cast<std::chrono::milliseconds>(current_time - start_time).count() > 3800) {
break;
}
// If a Hamiltonian path is found, we can stop.
if (best_path.size() == n) {
break;
}
run_id++;
std::vector<int> current_path;
current_path.reserve(n);
int current_node = start_node;
current_path.push_back(current_node);
visited_marker[current_node] = run_id;
while (true) {
int first_unvisited_idx = -1;
// Find the first unvisited neighbor in the sorted adjacency list.
for (size_t i = 0; i < adj[current_node].size(); ++i) {
if (visited_marker[adj[current_node][i]] != run_id) {
first_unvisited_idx = i;
break;
}
}
if (first_unvisited_idx == -1) {
break; // No unvisited neighbors, path is stuck.
}
// Collect all unvisited neighbors with the same maximum out-degree for random tie-breaking.
int max_deg = out_degree[adj[current_node][first_unvisited_idx]];
int last_candidate_idx = first_unvisited_idx;
for (size_t i = first_unvisited_idx + 1; i < adj[current_node].size(); ++i) {
int neighbor = adj[current_node][i];
if (visited_marker[neighbor] != run_id && out_degree[neighbor] == max_deg) {
last_candidate_idx = i;
} else {
break;
}
}
// Randomly pick one of the best candidates.
int choice_range_size = last_candidate_idx - first_unvisited_idx + 1;
int choice_offset = rng() % choice_range_size;
int choice_idx = first_unvisited_idx + choice_offset;
current_node = adj[current_node][choice_idx];
current_path.push_back(current_node);
visited_marker[current_node] = run_id;
}
// Update the best path if the current one is longer.
if (current_path.size() > best_path.size()) {
best_path = current_path;
}
}
if (best_path.empty() && n > 0) {
best_path.push_back(1);
}
std::cout << best_path.size() << "\n";
for (size_t i = 0; i < best_path.size(); ++i) {
std::cout << best_path[i] << (i == best_path.size() - 1 ? "" : " ");
}
std::cout << "\n";
}
int main() {
solve();
return 0;
} |