VOJ - VOSNET

Source: VOSNET
Tags: Graph

Problem:
Một mạng xã hội gồm N tài khoản và M mối quan hệ (u, v) cho biết tài khoản u và v biết nhau. Sau một tháng, một người sẽ quen hết tất cả những người có bạn chung với anh ta.
Ví dụ: A quen B, B quen C nhưng A không quen C, sau một tháng A sẽ quen C và một mối quan hệ mới được hình thành.
Sẽ đến 1 tháng mà không có một mối quan hệ mới nào được hình thành nữa, ta gọi đó là tháng bão hòa. Từ sau tháng đầu tiên đến sau tháng bão hòa, in ra số lượng các mối quan hệ mới được hình thành trong tháng.
N ≤ 3e3. M ≤ 6e3.

Ví dụ:
Input:
6 6
1 2
2 3
3 4
4 6
2 5
5 6

Output:
7 2 0

Explanation:
Các mối quan hệ mới theo mỗi tháng:
1. (1, 3), (1, 5), (2, 4), (2, 6), (3, 5), (3, 6), (4, 5);
2. (1, 4), (1, 6);
3. Đây là tháng bão hòa, không có mối quan hệ mới được tạo thành.

Solution:
Chúng ta có thể dễ dàng tìm đường đi ngắn nhất giữa mỗi cặp đỉnh bằng cách BFS mỗi đỉnh.
Nhận thấy rằng, qua mỗi tháng đường đi ngắn nhất giữa mỗi cặp đỉnh sẽ giảm đi một nửa!
Xét thử một đường đi từ 1 đến 5 như sau:

Sau tháng 1:

Sau tháng 2:

Ta có thể thấy rõ ràng độ dài đường ngắn nhất của 1 và 5 ban đầu là 4, sau 2 tháng, đã xuất hiện đường nối giữa 1 và 5! Vậy với mỗi độ dài đường ngắn nhất, gọi là d[u][v], ta tìm số k nhỏ nhất sao cho 2^k ≥ d[u][v], đó là số tháng để u nối với v, nói cách khác chính là số tháng mà mối quan hệ (u, v) được hình thành.
Độ phức tạp O(N * (N + M) + N * N)

Code:
#include <iostream>
#include <vector>
#include <queue>
#include <math.h>

using namespace std;

int n, m, d[3015][3015], cnt[3015];
vector <int> a[3015];
queue <int> bfs;

int main() {
    cin >> n >> m;
    for (int u, v; m--;)
        cin >> u >> v,
        a[u].push_back(v),
        a[v].push_back(u);
    for (int x = 1; x <= n; x++) {
        bfs.push(x);
        while (!bfs.empty()) {
            int u = bfs.front(); bfs.pop();
            for (int v: a[u])
                if (v != x && d[x][v] == 0)
                    d[x][v] = d[x][u] + 1,
                    bfs.push(v);
        }
    }
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            if (d[i][j]) ++cnt[int(ceil(log2(d[i][j])))];
    for (int i = 1; i <= n; i++) {
        cout << cnt[i] << ' ';
        if (cnt[i] == 0) return 0;
    }
}