Skip to content

README.md

Latest commit

 

History

History
131 lines (88 loc) · 3.84 KB

README.md

File metadata and controls

131 lines (88 loc) · 3.84 KB
Raw

Applied_Algorithms

Repo: tdvipp/Applied_Algorithms

Repository này tổng hợp các bài cài đặt/ôn tập thuật toán, được nhóm theo chủ đề.
Mỗi mục bên dưới liệt kê các file tương ứng để bạn dễ tìm.

Nếu bạn thấy hay hãy star repo này!!!

Buy me a coffee :)

257F58BE-72BE-4973-B44A-24525DA08D61_1_201_a

1) Graph algorithms / Lý thuyết đồ thị

1.1. MST (Minimum Spanning Tree)

  • Prim: Mo_phong_ly_thuyet_do_thi/prim_al.cpp
  • Kruskal + DSU/Union-Find: Mo_phong_ly_thuyet_do_thi/krushkal_union_find.cpp
  • (Bản khác/ghi chú): others/MST_KRUSKAL.cpp

1.2. Topological Sort

  • Mo_phong_ly_thuyet_do_thi/topo_sort.cpp

1.3. DFS numbering / low-link (phục vụ bridge/articulation)

  • Mo_phong_ly_thuyet_do_thi/build_num_and_low_array.cpp

1.4. Bridges & Articulation Points

  • Thuc_hanh_buoi_5/BRIDGES_ARTI_POINTS.cpp

1.5. Strongly Connected Components (SCC)

  • Thuc_hanh_buoi_5/STRONGLY_CONNECTED_COMPONENT.cpp

1.6. Bài toán đồ thị khác

  • Bus inter-city routing: Mo_phong_ly_thuyet_do_thi/BUS_INTER_CITY.cpp
  • Check bipartite graph (BFS + tô màu): others/check_bipartite_graph.cpp

2) BFS / DFS / Traversal

2.1. DFS (liệt kê theo thứ tự tăng dần bằng set)

  • others/DFS_LIST_SEQ_NODES_LEX.cpp

2.2. DFS dùng trong các bài đồ thị (bridge, SCC, low-link)

  • Thuc_hanh_buoi_5/BRIDGES_ARTI_POINTS.cpp
  • Thuc_hanh_buoi_5/STRONGLY_CONNECTED_COMPONENT.cpp
  • Mo_phong_ly_thuyet_do_thi/build_num_and_low_array.cpp

2.3. BFS

  • Check bipartite (tô màu 2 phía): others/check_bipartite_graph.cpp

3) Grid / Pathfinding / Traversal trên lưới

  • Maze solving (traversal trên grid): Thuc_hanh_buoi_1/maze.cpp

4) Range queries / Sparse-table style preprocessing

  • Range Minimum Query (RMQ): Thuc_hanh_buoi_1/range_minimum_query.cpp

5) Stack / Histogram / Maximal rectangle

  • Largest black sub-rectangle (thường giải bằng histogram + stack):
    Thuc_hanh_buoi_1/largest_black_subrectangle.cpp

6) Backtracking / Combinatorial search / Tối ưu ràng buộc

  • CBUS (dạng backtracking / TSP-like): Thuc_hanh_buoi_2/CBUS.cpp
  • BCA (phân công/điều kiện xung đột, backtracking + kiểm tra): Thuc_hanh_buoi_2/BCA.cpp
  • Hamilton cycle (brute-force/backtracking): others/HAM_CYCLE.cpp
  • TSP (backtracking/nhánh cận): others/TSP.cpp
  • Route planning (biến thể gần TSP): others/do_thi_route_planning.cpp
  • K-path (đếm/tìm đường đi độ dài k, dùng TRY/quay lui): others/do_thi_k_path.cpp
  • DIGITS (bài thi, quay lui gán chữ số): De_thi_giua_ky/De_1/bai_3_DIGITS.cpp

7) Counting / Đếm nghiệm / Phương trình nguyên

  • Count integer solutions of linear equation:
    Thuc_hanh_buoi_2/COUNT_INTEGER_LINEAR_EQUATION.cpp

8) Sorting / Divide-and-conquer / Counting (BIT-style)

  • Inversion counting: Thuc_hanh_buoi_3/INVERSION.cpp

9) Greedy / Subsequences / Searching

  • Max distance subsequence: Thuc_hanh_buoi_3/MAX_DISTANCE_SUB_SEQ.cpp
  • LIS (Longest Increasing Subsequence): Thuc_hanh_buoi_3/lis1.cpp

10) Prefix sums / Cumulative sums

  • Max even (subarray) theo ý tưởng cumulative sum:
    Thuc_hanh_buoi_4/MAX_EVEN_cusum.cpp

11) Scheduling / Optimization

  • Makespan scheduling: Thuc_hanh_buoi_5/MAKE_SPAN_SCHEDULE.cpp

12) Bộ đề / Luyện tập

  • Giữa kỳ: De_thi_giua_ky/
  • Cuối kỳ: De_thi_cuoi_ky/

Build & run (C++)

Bạn có thể build từng file độc lập:

g++ -std=c++17 -O2 -o main path/to/file.cpp
./main

Ví dụ:

g++ -std=c++17 -O2 -o main Thuc_hanh_buoi_5/BRIDGES_ARTI_POINTS.cpp
./main