ONBRIDGE - Online Bridge Searching
English | Vietnamese |
Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/onbridge
Cho một đồ thị N đỉnh, đánh số từ 0 đến N - 1. Ban đầu đồ thị không có cạnh nào. Lần lượt thêm vào đồ thị M cạnh vô hướng (u, v) với (0 <= u, v <= N - 1). Sau mỗi lần thêm 1 cạnh, in ra số lượng cầu hiện có trong đồ thị. Dữ liệu đảm bảo không có yêu cầu thêm vào 1 cạnh đã tồn tại, hoặc 1 cạnh nối 1 đỉnh với chính nó.
Input
Dòng đầu ghi số nguyên T (T <= 10) là số lượng bộ test. Mỗi bộ test bắt đầu bằng 2 số nguyên N (1 <= N <= 50000) và M (1 <= M <= 100000), theo sau là M dòng, mỗi dòng ghi 1 cặp số nguyên (u, v) thể hiện một yêu cầu thêm vào cạnh (u, v).
Output
Sau mỗi yêu cầu thêm cạnh, in ra 1 số nguyên trên 1 dòng là số lượng cầu hiện có trong đồ thị.
Example
Với dữ liệu:
1 5 10 3 0 0 2 1 0 1 3 1 4 2 4 4 0 2 1 2 3 3 4
Kết quả đúng là:
1 2 3 1 2 0 0 0 0 0
Added by: | Race with time |
Date: | 2012-03-06 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |