Đề QG mọi năm em nhận thấy là giới hạn các đỉnh ,cạnh thường là 10^5 và 2*10^5....

Cho em hỏi mình có phải dùng danh sách kề để biểu diễn đồ thị này không? với lại  khi định chiều đồ thị khi duyệt cạnh (u,v) thì mình phải bỏ cung (v,u) thì phải làm thế nào, vd như trong bài reform đề năm trước ,  trong đó nếu em muốn đánh dấu cái nào là cầu thì phải làm sao?

Theo mình:

  • Biểu diễn đồ thị thì tùy thuật toán mà có cách biểu diễn khác nhau, chẳng hạn sử dụng BFS, DFS thì mình thường tổ chức dưới dạng danh sách kề, còn Kruscal thì mình biểu diễn dưới dạng danh sách cạnh.
  • Việc đánh dấu bỏ cung ngược thì bạn có thể lưu lại vị trí cung ngược của mỗi cung trên danh sách kề rồi dùng mảng đánh dấu lại.