Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
2.3 kB
3
Indexable
Never
#include <iostream>
#define size 55
using namespace std;

int N, M;
int arr[size] = {}, nums;
int adj[size][size] = {};
int res, arr_res[size], length;

// Hàm sắp xếp mảng
void sort(int arr[], int nums) { 
    for(int i = 0; i < nums - 1; i++) {
        for(int j = i + 1; j < nums; j++) {
            if(arr[i] > arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

// Hàm tính tổng các phần tử từ vị trí start đến n
int sum(int arr[], int start, int n) {
    int res = 0;
    for(int i = start; i < n; i++)
        res += arr[i];
    return res;
}

int mark[size] = {};

// Hàm DFS để tìm chu trình
void dfs(int v, int visited[]) {
    visited[v] = mark[v] = 1;
    arr[nums++] = v;
    for(int i = 1; i <= N; i++) {
        if(adj[v][i] == 1) {
            if(visited[i] == 0) {
                dfs(i, visited);
            } else if(mark[i] == 1) {
                int start = 0; 
                while(start < nums && i != arr[start]) start++;
                int sum_ = sum(arr, start, nums);
                // Cập nhật kết quả
                if(res > sum_) {
                    res = sum_;
                    length = nums - start;
                    for(int j = 0; j < nums - start; j++)
                        arr_res[j] = arr[j + start];
                }
            }
        }
    }
    mark[v] = 0;
    nums--;
}

int main() {
    // Nhập số lượng đỉnh và cạnh
    cin >> N >> M;
    
    // Nhập các cạnh và tạo đồ thị
    for(int i = 0; i < M; i++) {
        int x, y; 
        cin >> x >> y;
        adj[x][y] = 1;
    }

    // Khởi tạo
    nums = 0;
    res = 999999;

    // Duyệt qua từng đỉnh để tìm chu trình
    for(int i = 1; i <= N; i++) {
        int visited[size] = {};
        dfs(i, visited);
    }

    // Sắp xếp và in kết quả
    sort(arr_res, length);
    for(int i = 0; i< length; i++)
           cout << arr_res[i] << ' ';
    cout << endl;

    // Reset
    for(int i = 0; i <= N; i++) {
        mark[i] = 0;
        for(int j = 0; j <= N; j++)
            adj[i][j] = 0;
    }

    return 0;
}
Leave a Comment