File size: 4,669 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 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 | #include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <queue>
void solve() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
int m;
std::cin >> n >> m;
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<std::vector<int>> rev_adj(n + 1);
std::vector<int> out_degree(n + 1, 0);
std::vector<int> in_degree(n + 1, 0);
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
rev_adj[v].push_back(u);
out_degree[u]++;
in_degree[v]++;
}
// Heuristic part 1: Compute a reverse topological sort order to guide greedy choices.
// This is equivalent to Kahn's algorithm on the reversed graph, which uses out-degrees
// of the original graph.
std::vector<int> topo_rev_pos(n + 1, -1);
{
std::vector<int> current_out_degree = out_degree;
std::queue<int> q;
for (int i = 1; i <= n; ++i) {
if (current_out_degree[i] == 0) {
q.push(i);
}
}
std::vector<int> topo_order;
while (!q.empty()) {
int u = q.front();
q.pop();
topo_order.push_back(u);
for (int v : rev_adj[u]) {
current_out_degree[v]--;
if (current_out_degree[v] == 0) {
q.push(v);
}
}
}
// Assign ranks. Nodes appearing earlier in topo_order are "sinks".
// We give them higher ranks to prioritize them in the greedy search.
for(size_t i = 0; i < topo_order.size(); ++i) {
topo_rev_pos[topo_order[i]] = topo_order.size() - 1 - i;
}
}
// Heuristic part 2: Greedy search from potential starting nodes.
// Best candidates for starting nodes are those with an in-degree of 0.
std::vector<int> start_nodes;
for (int i = 1; i <= n; ++i) {
if (in_degree[i] == 0) {
start_nodes.push_back(i);
}
}
// Fallback if no 0-in-degree nodes exist (due to cycles).
// Start from a node with the minimum in-degree.
if (start_nodes.empty() && n > 0) {
int min_in_degree = n + 1;
int best_start = -1;
for (int i = 1; i <= n; ++i) {
if (in_degree[i] < min_in_degree) {
min_in_degree = in_degree[i];
best_start = i;
}
}
if (best_start != -1) {
start_nodes.push_back(best_start);
}
}
std::vector<int> best_path;
for (int start_node : start_nodes) {
std::vector<int> current_path;
std::vector<bool> visited(n + 1, false);
int current_v = start_node;
while (current_v != -1 && !visited[current_v]) {
visited[current_v] = true;
current_path.push_back(current_v);
int next_v = -1;
int best_pos = -1;
for (int neighbor : adj[current_v]) {
if (!visited[neighbor]) {
if (topo_rev_pos[neighbor] > best_pos) {
best_pos = topo_rev_pos[neighbor];
next_v = neighbor;
}
}
}
current_v = next_v;
}
if (current_path.size() > best_path.size()) {
best_path = current_path;
}
}
// A final fallback if no path was constructed (e.g., if n>0 but start_nodes was empty).
if (best_path.empty() && n > 0) {
int start_node = 1;
std::vector<bool> visited(n + 1, false);
int current_v = start_node;
while (current_v != -1 && !visited[current_v]) {
visited[current_v] = true;
best_path.push_back(current_v);
int next_v = -1;
int best_pos = -1;
for (int neighbor : adj[current_v]) {
if (!visited[neighbor]) {
if (topo_rev_pos[neighbor] > best_pos) {
best_pos = topo_rev_pos[neighbor];
next_v = neighbor;
}
}
}
current_v = next_v;
}
}
std::cout << best_path.size() << "\n";
bool first = true;
for (int node : best_path) {
if (!first) {
std::cout << " ";
}
std::cout << node;
first = false;
}
std::cout << "\n";
}
int main() {
solve();
return 0;
} |