Hugging Face's logo

JustinTX
/
shinka-backup

Model card Files
xet
 Community
shinka-backup
File size: 4,603 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
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>

using namespace std;

// Maximum number of vertices as per constraints
const int MAXN = 500005;

// Graph and degree information
vector<int> adj[MAXN];
int in_degree[MAXN];
int out_degree[MAXN];

// Visited array for DFS
bool visited[MAXN];
// To keep track of the current neighbor index for each node during iterative DFS
int cur_edge[MAXN]; 

// Path storage
vector<int> best_path;
vector<int> current_path;

int n, m;
vector<int> a(10); // Scoring parameters (unused in logic)

// Comparator to sort neighbors:
// 1. Prefer neighbors with lower in-degree (harder to reach later)
// 2. Prefer neighbors that are not dead ends (out-degree > 0)
// 3. Prefer neighbors with lower out-degree (Warnsdorff's heuristic)
bool compareNeighbors(int u, int v) {
    if (in_degree[u] != in_degree[v])
        return in_degree[u] < in_degree[v];
    
    bool term_u = (out_degree[u] == 0);
    bool term_v = (out_degree[v] == 0);
    if (term_u != term_v) return !term_u; // Non-terminal nodes come first
    
    return out_degree[u] < out_degree[v];
}

// Comparator for choosing start nodes
bool compareStartNodes(int u, int v) {
    if (in_degree[u] != in_degree[v])
        return in_degree[u] < in_degree[v];
    return out_degree[u] < out_degree[v];
}

int main() {
    // Optimize I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n >> m)) return 0;
    
    for (int i = 0; i < 10; ++i) cin >> a[i];

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        out_degree[u]++;
        in_degree[v]++;
    }

    // Sort adjacency lists based on heuristic
    for (int i = 1; i <= n; ++i) {
        sort(adj[i].begin(), adj[i].end(), compareNeighbors);
    }

    // Identify potential start nodes
    vector<int> start_nodes;
    start_nodes.reserve(n);
    for (int i = 1; i <= n; ++i) {
        start_nodes.push_back(i);
    }
    
    sort(start_nodes.begin(), start_nodes.end(), compareStartNodes);

    // Heuristic: if nodes with in-degree 0 exist, start must be one of them.
    // Otherwise, try a few best candidates.
    int candidates_to_try = min(n, 20); 
    int zero_in_count = 0;
    for(int u : start_nodes) if(in_degree[u] == 0) zero_in_count++;
    if(zero_in_count > 0) candidates_to_try = zero_in_count; 

    // Time management
    clock_t start_time = clock();
    double time_limit = 3.8; 
    long long operations = 0;
    
    for (int k = 0; k < candidates_to_try; ++k) {
        int start_node = start_nodes[k];
        
        current_path.clear();
        current_path.reserve(n);
        
        // Initialize DFS from start_node
        current_path.push_back(start_node);
        visited[start_node] = true;
        cur_edge[start_node] = 0;
        
        if (current_path.size() > best_path.size()) {
            best_path = current_path;
        }

        // Iterative DFS
        while (!current_path.empty()) {
            operations++;
            // Check time limit periodically
            if ((operations & 65535) == 0) {
                if ((double)(clock() - start_time) / CLOCKS_PER_SEC > time_limit) goto end_search;
            }

            int u = current_path.back();
            
            // If Hamiltonian path found
            if (current_path.size() == n) {
                best_path = current_path;
                goto end_search; 
            }
            
            bool found = false;
            // Try to find an unvisited neighbor
            while (cur_edge[u] < adj[u].size()) {
                int v = adj[u][cur_edge[u]];
                cur_edge[u]++;
                if (!visited[v]) {
                    visited[v] = true;
                    current_path.push_back(v);
                    cur_edge[v] = 0; // Reset iterator for the new node
                    found = true;
                    if (current_path.size() > best_path.size()) {
                        best_path = current_path;
                    }
                    break; // Successfully pushed a neighbor
                }
            }

            if (!found) {
                // Backtrack
                visited[u] = false;
                cur_edge[u] = 0; // Reset iterator for future visits
                current_path.pop_back();
            }
        }
    }

end_search:
    cout << best_path.size() << "\n";
    for (int i = 0; i < best_path.size(); ++i) {
        cout << best_path[i] << (i == best_path.size() - 1 ? "" : " ");
    }
    cout << "\n";

    return 0;
}