Graph fundamentals

A graph models relationships. Vertices are objects; edges connect them. Roads, friendships, dependencies, and game states can all become graphs.

Prerequisites: Basic C++ input/output, vectors, loops, and the preceding graph lessons.

Build the idea

1. A directed edge goes one way. An undirected edge goes both ways.
2. A weighted edge stores a cost. An unweighted edge counts as one step.
3. A path follows edges. A cycle returns to its starting vertex. A connected component is a maximal connected set.
4. We label vertices 1 through n. An adjacency list stores the neighbors of each vertex.
5. graph[v] stores neighbors of v. Each undirected edge is inserted at both endpoints, so the sum of degrees equals 2m.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: graph[v] stores neighbors of v. Each undirected edge is inserted at both endpoints, so the
// sum of degrees equals 2m.
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<int>>graph(n+1);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int vertex=1;vertex<=n;vertex++){
        cout<<graph[vertex].size()<<'\n';
    }
}

Complexity analysis

O(V + E) time and space to build adjacency lists.

Example input and output

Read n m (n≥1), then m undirected edges a b with labels 1..n. Print the degree of each vertex on a separate line. A loop contributes two adjacency entries.

Input

4 3
1 2
1 4
2 3

Output

2
2
1
1

Vertices 1 and 2 each meet two edges; vertices 3 and 4 each meet one.

Practical applications

Use adjacency lists for sparse graphs and degree queries. Store only the outgoing direction for a directed graph.

Check your understanding

An undirected graph has 5 edges. How many adjacency-list entries does it have?

Put it into practice

Read an undirected graph and print the degree of every vertex.