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:
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:
#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 \(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:
#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:
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:
#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:
#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 \(O(n+mlogm)\), significantly better than a naive \(O(nm)\) implementation.
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
