Hiểu bài toán

Cho một đồ thị vô hướng có n đỉnh và m cạnh. Yêu cầu với mỗi đỉnh i (từ 1 đến n), in ra danh sách các đỉnh kề của nó trên cùng một dòng, cách nhau bởi dấu cách, và kết thúc bằng số 0. Đồ thị có thể có khuyên (cạnh nối một đỉnh với chính nó) và các cạnh song song, nhưng theo các giải pháp nộp vào, các cạnh song song và khuyên có thể được xử lý khác nhau. Tuy nhiên, dựa trên các giải pháp mẫu, bài toán yêu cầu chỉ in ra các đỉnh kề khác chính nó và không in lại các cạnh trùng lặp (trong giải pháp 1 và 2) hoặc có thể in trùng lặp (giải pháp 3). Tuy nhiên, với input là danh sách các cạnh, ta cần xây dựng danh sách kề và in ra.

Các cách tiếp cận

Cách Danh sách kề cơ bản

#include <bits/stdc++.h>
using namespace std;
vector<int> adj[1005];
int main() {
    freopen("canhnhau.INP", "r", stdin);
    freopen("canhnhau.OUT", "w", stdout);
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        if (u != v) {
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    }
    for (int i = 1; i <= N; ++i) {
        auto &nbr = adj[i];
        for (int v : nbr) {
            cout << v << ' ';
        }
        cout << "0\n";
    }
    return 0;
}

• Time Complexity: O(N + M)
• Space Complexity: O(N + M)

Giải pháp này xây dựng danh sách kề bằng cách duyệt qua từng cạnh. Nếu đỉnh đầu và cuối khác nhau, ta thêm v vào adj[u] và u vào adj[v]. Sau đó, với mỗi đỉnh, ta duyệt qua danh sách kề và in ra các đỉnh kề, kết thúc bằng 0. Tuy nhiên, nếu có cạnh song song, danh sách kề sẽ chứa phần tử trùng lặp, dẫn đến in ra nhiều lần. Giải pháp này không loại bỏ cạnh song song, nên kết quả có thể sai nếu input có cạnh song song và yêu cầu chỉ in một lần.

Cách Loại bỏ cạnh song song bằng set

#include <bits/stdc++.h>
using namespace std;
set<int> adj[1005];
int main() {
    freopen("canhnhau.INP", "r", stdin);
    freopen("canhnhau.OUT", "w", stdout);
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        if (u != v) {
            adj[u].insert(v);
            adj[v].insert(u);
        }
    }
    for (int i = 1; i <= N; ++i) {
        for (int v : adj[i]) {
            cout << v << ' ';
        }
        cout << "0\n";
    }
    return 0;
}

• Time Complexity: O(M log N)
• Space Complexity: O(M)

Sử dụng set cho danh sách kề để tự động loại bỏ các cạnh song song. Mỗi cạnh được thêm vào set với chi phí O(log N). Sau đó, duyệt set để in ra các đỉnh kề. Cách này đảm bảo mỗi đỉnh kề chỉ được in một lần, phù hợp với các giải pháp mẫu 1 và 2.

Cách Xử lý và loại bỏ trùng lặp sau khi nhập

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen("CANHNHAU.inp", "r", stdin);
    freopen("CANHNHAU.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    vector <vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        sort(adj[i].begin(), adj[i].end());
        adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
        for (auto x : adj[i])
            if (x != i)
                cout << x << ' ';
        cout << 0 << '\n';
    }
}

• Time Complexity: O(M + N log N)
• Space Complexity: O(M)

Giải pháp này tương tự giải pháp 1 nhưng sau khi nhập xong, nó sort và dùng unique để loại bỏ các phần tử trùng lặp trong danh sách kề của mỗi đỉnh. Điều này đảm bảo mỗi đỉnh kề chỉ được in một lần. Tuy nhiên, giải pháp mẫu 3 không thực hiện bước này mà chỉ kiểm tra x != i, nhưng vẫn có thể in trùng lặp nếu có cạnh song song. Tuy nhiên, với các test thông thường, cách này có thể chấp nhận được.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán yêu cầu in ra danh sách các đỉnh kề của mỗi đỉnh, kết thúc bằng 0.
• Cần xử lý các cạnh song song để không in trùng lặp các đỉnh kề.
• Có thể sử dụng vector và loại bỏ trùng lặp sau khi nhập, hoặc sử dụng set để tự động loại bỏ.

Lỗi thường gặp

• Quên kiểm tra đỉnh đầu và cuối khác nhau, dẫn đến in ra chính nó (nếu không muốn in khuyên).
• Không xử lý cạnh song song, dẫn đến in ra nhiều lần cùng một đỉnh kề.
• Lỗi cú pháp khi in ra 0 ở cuối mỗi dòng.