C++ forward_star.cpp
UTF-8 · C++20 · LF
#include <iostream>
#include <cstring>
#include <utility>
using namespace std;

const int MAXN = 1005;
const int MAXM = 2005;

// 用 PII 代替结构体:first 存终点(to),second 存上一条边下标(next)
typedef pair<int, int> PII;
PII edge[MAXM];

int head[MAXN]; // 存每个点最新连出的边的下标
int cnt = 0;    // 当前边的总数

// 初始化
void init(int n) {
    memset(head, -1, sizeof(head));
    cnt = 0;
}

// 加边函数(单链表头插法)
void add(int u, int v) {
    edge[cnt].first  = v;        // 终点
    edge[cnt].second = head[u];  // 同起点的上一条边
    head[u] = cnt++;
}

// 遍历从 u 出发能到达的所有点
void traverse(int u) {
    cout << "从 " << u << " 号点出发能到的点: ";
    for (int i = head[u]; i != -1; i = edge[i].second) {
        cout << edge[i].first << " ";
    }
    cout << "\n";
}

int main() {
    int n = 4, m = 5;
    init(n);

    // 样例数据:4个点,5条边
    // 1 -> 2
    // 1 -> 3
    // 2 -> 4
    // 3 -> 2
    // 3 -> 4
    add(1, 2);
    add(1, 3);
    add(2, 4);
    add(3, 2);
    add(3, 4);

    for (int i = 1; i <= n; i++) {
        traverse(i);
    }

    return 0;
}