Hugging Face's logo

JustinTX
/
shinka-backup

Model card Files
xet
 Community
shinka-backup
File size: 2,941 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
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <deque>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    std::cin >> n >> m;

    // The scoring parameters are not used by the logic, but must be read from input.
    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> in_degree(n + 1, 0);
    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);
        rev_adj[v].push_back(u);
        out_degree[u]++;
        in_degree[v]++;
    }

    // Heuristically find a good starting node.
    int start_node = 1;
    long long max_score = -2000000001LL; 
    for (int i = 1; i <= n; ++i) {
        long long current_score = (long long)out_degree[i] - in_degree[i];
        if (current_score > max_score) {
            max_score = current_score;
            start_node = i;
        }
    }

    std::deque<int> path;
    path.push_back(start_node);
    std::vector<bool> visited(n + 1, false);
    visited[start_node] = true;

    while (path.size() < n) {
        bool extended = false;

        // Try to extend forward from the back of the path.
        int u_fwd = path.back();
        int best_v_fwd = -1;
        int min_in = n + 1;

        for (int v : adj[u_fwd]) {
            if (!visited[v]) {
                if (best_v_fwd == -1 || in_degree[v] < min_in || (in_degree[v] == min_in && v < best_v_fwd)) {
                    min_in = in_degree[v];
                    best_v_fwd = v;
                }
            }
        }

        if (best_v_fwd != -1) {
            path.push_back(best_v_fwd);
            visited[best_v_fwd] = true;
            extended = true;
            continue;
        }

        // If forward extension fails, try to extend backward from the front of the path.
        int u_bwd = path.front();
        int best_v_bwd = -1;
        int min_out = n + 1;

        for (int v : rev_adj[u_bwd]) {
            if (!visited[v]) {
                if (best_v_bwd == -1 || out_degree[v] < min_out || (out_degree[v] == min_out && v < best_v_bwd)) {
                    min_out = out_degree[v];
                    best_v_bwd = v;
                }
            }
        }
        
        if (best_v_bwd != -1) {
            path.push_front(best_v_bwd);
            visited[best_v_bwd] = true;
            extended = true;
            continue;
        }

        // If unable to extend in either direction, break.
        if (!extended) {
            break;
        }
    }

    std::cout << path.size() << "\n";
    for (size_t i = 0; i < path.size(); ++i) {
        std::cout << path[i] << (i == path.size() - 1 ? "" : " ");
    }
    std::cout << "\n";

    return 0;
}