Grade 11 · Undirected graphsCitește în română

Adjacency lists

Original: Listele de adiacență

O(log n)C++1757 lines1 example

The idea

For every node we store only the list of its neighbours. The edge [x, y] is added twice: y to the list of x and x to the list of y. The memory used is proportional to n + m (not to n², as with the matrix), which matters for large graphs with few edges. The length of node i's list is its degree. The lists are sorted so that the neighbours are printed in increasing order.

Original description (Romanian)

Pentru fiecare nod reținem doar lista vecinilor lui. Muchia [x, y] se adaugă de două ori: y în lista lui x și x în lista lui y. Memoria folosită este proporțională cu n + m (nu cu n², ca la matrice), ceea ce contează pentru grafuri mari cu puține muchii. Lungimea listei nodului i este gradul lui. Listele se sortează ca vecinii să fie afișați în ordine crescătoare.

Complexity
O(n + m log m)
Grade
Grade 11 (Clasa a XI-a)

Examples

Example 1

Input

5 5
1 2
1 5
2 3
4 5
2 5

Expected output

1: 2 5
2: 1 3 5
3: 2
4: 5
5: 1 2 4

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

liste-de-adiacenta.cpp
/*
 * Titlu: Listele de adiacență
 * Clasa: 11
 * Capitol: Grafuri neorientate
 * Descriere: Pentru fiecare nod reținem doar lista vecinilor lui. Muchia [x, y] se adaugă
 *            de două ori: y în lista lui x și x în lista lui y. Memoria folosită este
 *            proporțională cu n + m (nu cu n², ca la matrice), ceea ce contează pentru
 *            grafuri mari cu puține muchii. Lungimea listei nodului i este gradul lui.
 *            Listele se sortează ca vecinii să fie afișați în ordine crescătoare.
 * Complexitate: O(n + m log m)
 *
 * Exemplu
 * Intrare:
 * 5 5
 * 1 2
 * 1 5
 * 2 3
 * 4 5
 * 2 5
 * Ieșire:
 * 1: 2 5
 * 2: 1 3 5
 * 3: 2
 * 4: 5
 * 5: 1 2 4
 */
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> vecini[100005];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int k = 1; k <= m; k++)
    {
        int x, y;
        cin >> x >> y;
        vecini[x].push_back(y);
        vecini[y].push_back(x);
    }
    for (int i = 1; i <= n; i++)
    {
        sort(vecini[i].begin(), vecini[i].end());
        cout << i << ':';
        for (int v : vecini[i])
        {
            cout << ' ' << v;
        }
        cout << '\n';
    }
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.