Submission #1257657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257657		anha3k25cvp	Potemkin cycle (CEOI15_indcyc)	C++20	30 / 100	9 ms	1352 KiB

indcyc

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

void solve() {
    int n, m;
    std::cin >> n >> m;

    // Sử dụng vector<vector<int>> làm danh sách kề
    std::vector<std::vector<int>> adj(n + 1);
    // Sử dụng vector<vector<bool>> làm ma trận kề để kiểm tra cạnh O(1)
    std::vector<std::vector<bool>> has_edge(n + 1, std::vector<bool>(n + 1, false));

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        has_edge[u][v] = has_edge[v][u] = true;
    }

    // Lặp qua mỗi đỉnh u, coi nó là "đỉnh" của chu trình
    for (int u = 1; u <= n; ++u) {
        if (adj[u].size() < 2) {
            continue; // Cần ít nhất 2 hàng xóm để tạo thành cặp (v, w)
        }

        // Lặp qua tất cả các cặp hàng xóm (v, w) của u
        for (size_t i = 0; i < adj[u].size(); ++i) {
            for (size_t j = i + 1; j < adj[u].size(); ++j) {
                int v = adj[u][i];
                int w = adj[u][j];

                // Nếu v và w nối trực tiếp, sẽ tạo thành chu trình 3 (u-v-w-u).
                // Bỏ qua vì yêu cầu chu trình có ít nhất 4 đỉnh.
                if (has_edge[v][w]) {
                    continue;
                }

                // Tìm đường đi ngắn nhất từ v đến w không đi qua u bằng BFS
                std::queue<int> q;
                std::vector<int> parent(n + 1, 0);
                std::vector<bool> visited(n + 1, false);

                q.push(v);
                visited[u] = true; // Không được đi qua u
                visited[v] = true;
                parent[v] = -1; // Đánh dấu điểm bắt đầu để dừng truy vết

                bool path_found = false;
                while (!q.empty()) {
                    int curr = q.front();
                    q.pop();

                    if (curr == w) {
                        path_found = true;
                        break;
                    }

                    for (int neighbor : adj[curr]) {
                        if (!visited[neighbor]) {
                            visited[neighbor] = true;
                            parent[neighbor] = curr;
                            q.push(neighbor);
                        }
                    }
                }

                if (path_found) {
                    // Đã tìm thấy một chu trình hợp lệ. Dựng lại đường đi.
                    std::vector<int> path;
                    int curr = w;
                    while (curr != -1) {
                        path.push_back(curr);
                        curr = parent[curr];
                    }
                    std::reverse(path.begin(), path.end());

                    // In kết quả theo thứ tự u -> v -> ... -> w
                    std::cout << u << " ";
                    for (size_t k = 0; k < path.size(); ++k) {
                        std::cout << path[k] << (k == path.size() - 1 ? "" : " ");
                    }
                    std::cout << std::endl;
                    return; // Kết thúc chương trình vì đã tìm được 1 đáp án
                }
            }
        }
    }

    // Nếu các vòng lặp kết thúc mà không tìm thấy, in "no"
    std::cout << "no" << std::endl;
}

int main() {
    // Tăng tốc độ nhập xuất
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    solve();

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10