Cặp đỉnh một chiều
Points
15
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho đồ thị có hướng đơn giản gồm $N$ đỉnh và $M$ cung (không có khuyên, không có cung song song cùng hướng).
Một cặp đỉnh không thứ tự ${u, v}$ ($u < v$) được gọi là một chiều nếu tồn tại cung $u \to v$ hoặc cung $v \to u$, nhưng không tồn tại cả hai.
Ngoài ra, độ chênh lệch của một đỉnh $u$ được định nghĩa là $\text{outdeg}(u) - \text{indeg}(u)$ (bậc ra trừ bậc vào).
Hãy tìm:
- Số lượng cặp đỉnh một chiều.
- Đỉnh có độ chênh lệch lớn nhất (nếu có nhiều đỉnh cùng đạt giá trị lớn nhất, chọn đỉnh có chỉ số nhỏ nhất).
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$).
- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$, $u \ne v$) mô tả một cung có hướng $u \to v$.
Dữ liệu ra
- In ra hai số nguyên cách nhau bởi dấu cách: số cặp đỉnh một chiều và đỉnh có độ chênh lệch lớn nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 4 1 2 2 1 2 3 3 4 |
2 2 |
| 3 3 1 2 2 3 3 1 |
3 1 |
Giới hạn
- $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$.
Community Discussion