Graph Implementation
====================
In this section, we aim to input and store a graph in a computer. Modeling
graphs in computers allows us to leverage their immense processing power to
implement theoretical methods and algorithms. In programming competitions,
many problems are graph-related, and solving them requires properly inputting
and storing the graph.

How is the graph given as input?
--------------------------------
A standard input format commonly used in competition problems is as follows:
The first line contains the number of vertices and edges. Subsequent lines
each specify the two endpoints of an edge. For example:

.. code-block:: cpp

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

This represents a graph with 5 vertices and 6 edges. For instance, vertex 4
has a degree of 3. You can visualize this graph using the web tool at
https://csacademy.com/app/graph_editor/.

Adjacency List
--------------
While we could store the graph as an array of edges, this is inefficient.
Accessing a vertex's neighbors would require traversing all edges, which is
unacceptable for many applications.

A better approach is the adjacency list. Here, we maintain a dynamic array
(vector in C++) for each vertex to store its neighbors. The code implementation
looks like this:

.. code-block:: cpp

    #include <bits/stdc++.h>
    using namespace std;
    
    const int M = 1e5 + 5;  // The maximum number of vertices which is specified in the problem's statement

    vector<int> list_peyvandi[M];

    int main() {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= m; i += 1) {
            int u, v;
            cin >> u >> v;
            list_peyvandi[u].push_back(v);
            list_peyvandi[v].push_back(u);
        }
    }


Advantages include:
1. Neighbor traversal in O(degree) time
2. Memory and time complexity of :math:`O(N+E)` (sum of degrees equals twice the edge count)
This linear complexity is optimal as input processing itself requires this time.

Extracting Graph Information
----------------------------
Let's calculate key graph metrics: vertex degrees, neighbors, and min/max degrees.
Try implementing this yourself before viewing the code:

.. code-block:: cpp

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

    const int M = 1e5 + 5;  // Maximum possible number of vertices as specified in the problem statement

    vector<int> list_peyvandi[M];

    int main() {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= m; ++i) {
            int u, v;
            cin >> u >> v;
            list_peyvandi[u].push_back(v);
            list_peyvandi[v].push_back(u);
        }
        int dmin = M + 5;
        int dmax = -1;
        for (int u = 1; u <= n; ++u) {
            cout << "Rase shomare: " << u << "\n";
            int d = list_peyvandi[u].size();
            cout << "Daraje: " << d << "\n";
            if (dmin > d) dmin = d;
            if (dmax < d) dmax = d;
            cout << "Hamsaye ha: ";
            for (int v : list_peyvandi[u]) {
                cout << v << " ";
            }
            cout << "\n";
        }
        cout << "Delta koochak: " << dmin << "\n";
        cout << "Delta bozorg: " << dmax << "\n";
        return 0;
    }


Extended Example
----------------
Consider this problem: A garden with trees connected by roads. Each road has
a traversal time, and each tree has apples. We want to collect maximum apples
within k minutes. Input format:

.. code-block:: cpp

 5 6 43.2
 1 2 100 5 3
 1 2 20
 1 3 3.5
 1 4 7.1
 2 5 100.2
 4 5 31
 3 4 1.1

To store edge weights, we modify our adjacency list to store edge indices and
maintain separate arrays for edge data. Here's the implementation:

.. code-block:: cpp

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

    const int Mras = 1e5 + 5;  // Maximum possible number of vertices as specified in the problem statement
    const int Myal = 3e5 + 5;  // Maximum possible number of edges as specified in the problem statement

    vector<int> list_peyvandi[Mras];
    int sib[Mras];
    int u[Myal], v[Myal];
    double zaman[Myal];

    int main() {
        int n, m;
        cin >> n >> m;
        for (int e = 1; e <= m; ++e) {  // 'e' is the edge index
            int x, y;
            cin >> x >> y;
            list_peyvandi[x].push_back(e);  // Note that this differs from the previous version
            list_peyvandi[y].push_back(e);  // The edge index is stored
        }
        // Next, we print the neighbors of each vertex
        for (int x = 1; x <= n; ++x) {
            cout << "Vertex number: " << x << "\n";
            cout << "Neighbors:\n";
            for (int e : list_peyvandi[x]) {
                int y = u[e] ^ v[e] ^ x;  // Compute the other endpoint
                // Alternative implementations that would also work:
                // y = u[e] + v[e] - x;
                // y = (u[e] == x ? v[e] : u[e]);
                cout << " neighbor = " << y << ", time = " << zaman[e] << "\n";
            }
        }
        return 0;
    }


Practical Algorithm
-------------------
Let's implement a greedy solution for the apple collection problem. The
algorithm picks the shortest available edge until time runs out:

.. code-block:: cpp

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

    const int Mras = 1e5 + 5;   // Maximum possible number of vertices as specified in the problem statement
    const int Myal = 3e5 + 5;   // Maximum possible number of edges as specified in the problem statement

    vector<int> list_peyvandi[Mras];
    int sib[Mras];
    int u[Myal], v[Myal];
    double zaman[Myal];
    bool chide[Mras];

    int main() {
        int n, m;
        cin >> n >> m;
        for (int e = 1; e <= m; ++e) {  // 'e' is the edge index
            int x, y;
            cin >> x >> y;
            list_peyvandi[x].push_back(e);  // Note that this differs from the previous version
            list_peyvandi[y].push_back(e);  // The edge index is stored
        }
        // Sort adjacency lists by time
        for (int x = 1; x <= n; ++x) {
            sort(
                list_peyvandi[x].begin(),
                list_peyvandi[x].end(),
                [](int a, int b) {
                    return zaman[a] < zaman[b];
                }
            );
        }
        int cur = 1;   // We consider vertex 1 as the starting vertex
        int score = 0; // Accumulated score is stored here
        // WARNING: 'k' is used below but never declared
        while (k > 0) {
            chide[cur] = true;
            score += sib[cur];
            bool berim = false;
            int koja = -1;
            for (int e : list_peyvandi[cur]) {
                int nxt = u[e] ^ v[e] ^ cur;  // Compute the other endpoint
                if (chide[nxt]) continue;
                if (zaman[e] > k) break;
                berim = true;
                koja = nxt;
                k -= zaman[e];
                break;
            }
            if (!berim) break;
            cur = koja;
        }
        cout << score;
        return 0;
    }


Note: This greedy approach isn't optimal but demonstrates adjacency list usage.
Time complexity is :math:`O(n+mlogm)`, significantly better than a naive
:math:`O(nm)` implementation.