1. 인접 행렬

   int adj[N][N] 형태로, adj[i][j]가 i -> j 간선의 개수나 가중치를 나타냅니다.

   공간복잡도가 $O(N^2)$이라 잘 쓰이지 않습니다. 아주 가끔 플로이드 워셜 같은 곳에서 쓰이긴 합니다.

2. 인접 리스트

   vector<int> adj[N] 형태로, 각 노드마다 인접한 노드의 번호를 저장하는 방식입니다.

   다만, std::vector의 구현 특성상 간선 개수의 최대 두 배 만큼의 메모리를 필요로 합니다.

3. 중국인

struct Graph {
		static constexpr int N; // 정점 개수
    static constexpr int M; // 간선 개수
    int cnt = 0, y[M+2], nxt[M+2], fst[N];
    
    void add(int a, int b){
        y[++cnt] = b, nxt[cnt] = fst[a], fst[a] = cnt;
    }
} g;

임의의 중국인의 코드에서 발견한 방법입니다. 정확히 필요한 만큼의 메모리만을 사용해 그래프를 저장할 수 있습니다.

변수들이 가지는 의미는 다음과 같습니다.

y[i]: i번째로 추가된 간선의 도착 노드 번호

nxt[i] : i번째 간선이 a → b라고 했을 때, 노드 a에서 나가는 다음 간선의 번호

fst[i] : 노드 i에서 나가는 간선 중 첫 번째 간선의 번호

add(a, b) : 단방향 간선 a -> b를 추가

예시 코드) 트리에서의 dfs

void dfs(int x, int pre){
    for(int i = g.fst[x]; i; i = g.nxt[i]){
        int y = g.y[i];
        if (y != pre) dfs(y, x);
    }
}