Untitled
unknown
plain_text
a year ago
2.3 kB
7
Indexable
#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; }
Editor is loading...
Leave a Comment