Mật Độ Đồ Thị

Buổi 17 — Biểu diễn Đồ thị Implementation Mathematics
Points
42
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho một đồ thị vô hướng đơn gồm $N$ đỉnh và $M$ cạnh. Mật độ (density) của đồ thị được định nghĩa là $D = \frac{2M}{N(N-1)}$ với $N \ge 2$. Hãy tính và in ra mật độ dưới dạng phân số tối giản $p/q$. Nếu $N = 1$, in 0/1.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N$ và $M$ ($1 \le N \le 10^5$, $0 \le M \le \min(2 \times 10^5, N(N-1)/2)$).
  • $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ $v$.
Dữ liệu ra
  • In phân số tối giản $p/q$ biểu diễn mật độ đồ thị.
Ví dụ
Input Output
4 3\n1 2\n2 3\n3 4 1/2
Giới hạn
  • $1 \le N \le 10^5$
  • $0 \le M \le \min(2 \times 10^5, N(N-1)/2)$
Draft saved