Count the Edges in an Undirected Graph

Given an undirected graph as an adjacency list, return its number of edges. In an undirected adjacency list, each edge u — v is stored twice: v appears in adj[u] and u appears in adj[v].

Example

graph LR
    0 --- 1
    0 --- 2
    1 --- 2
    2 --- 3

adj = [[1, 2], [0, 2], [0, 1, 3], [2]]
Output: 4

Brute force: collect each edge once in a set

Walk every adjacency list, and write each edge in a normalized form (min, max), so that 0 — 1 found from vertex 0 and 1 — 0 found from vertex 1 become the same pair. The set's size is the number of distinct edges.

Walkthrough:

Four new pairs, so four edges.

Java has no tuple type, so each normalized pair is stored as a List<Integer> of two elements. List implements equals and hashCode by content, so two lists with the same elements count as one set entry. The graph is a List<List<Integer>>: entry u is the list of neighbors of u.

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    static int countEdges(List<List<Integer>> adj) {
        Set<List<Integer>> edges = new HashSet<>();
        for (int u = 0; u < adj.size(); u++) {
            for (int v : adj.get(u)) {
                edges.add(List.of(Math.min(u, v), Math.max(u, v)));
            }
        }
        return edges.size();
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = List.of(List.of(1, 2), List.of(0, 2), List.of(0, 1, 3), List.of(2));
        System.out.println(countEdges(adj));
    }
}

4

Time: O(V + E). Space: O(E) for the set.

Optimal: sum the degrees and halve

Each edge adds 1 to the degree of both of its endpoints, so the sum of all degrees is exactly 2E. This is called the handshake lemma: count the handshakes at a party by asking everyone how many hands they shook, then divide by two. A vertex's degree is the length of its adjacency list.

For the example, the degrees are 2 + 2 + 3 + 1 = 8, so E = 8 / 2 = 4.

import java.util.List;

public class Main {
    static int countEdges(List<List<Integer>> adj) {
        int degreeSum = 0;
        for (List<Integer> neighbors : adj) degreeSum += neighbors.size();
        return degreeSum / 2;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = List.of(List.of(1, 2), List.of(0, 2), List.of(0, 1, 3), List.of(2));
        System.out.println(countEdges(adj));
        System.out.println(countEdges(List.of(List.of(), List.of()))); // two vertices, no edges
    }
}

4
0

Time: O(V): List.size() is O(1), so each list costs one step, however long it is. Space: O(1).

Which to use

The degree sum assumes a well-formed undirected list: every edge stored exactly twice, and no duplicates. The set version is the safer choice when the input may be messy:

• Duplicate edges (1 listed twice in adj[0]) are counted once by the set.
• Edges stored in only one direction are still counted once by the set, but the degree sum would count them as half an edge.
• Self-loops v — v are usually stored once in adj[v]. The set counts them once. The degree-sum formula needs them stored twice.

For a directed graph, every edge is stored once, so the count is the degree sum, without halving.