链式前向星建图与搜索

很少使用这种建图法。

dfs：标准复杂度为 $(O(N+M))$。节点子节点的数量包含它自己（至少为 $1$），深度从 $0$ 开始（根节点深度为 $0$）。

bfs：深度从 $1$ 开始（根节点深度为 $1$）。

topsort：有向无环图（包括非联通）才拥有完整的拓扑序列（故该算法也可用于判断图中是否存在环）。每次找到入度为 $0$ 的点并将其放入待查找队列。

假设： 图顶点编号为 $1\sim n$，保存结构维持原有的链式前向星（以 1 为基准索引）。

const int N = 1e5 + 7, M = 1e6 + 7;

int tot, h[N], ver[M], ne[M];
int deg[N], vis[N], dis[N], siz[N];
vector<int> a; // DFS 序

void clear(int n) {
    tot = 0;
    a.clear();
    for (int i = 1; i <= n; ++i) {
        h[i] = deg[i] = vis[i] = dis[i] = siz[i] = 0;
    }
}

void add(int x, int y) {
    ver[++tot] = y;
    ne[tot] = h[x];
    h[x] = tot;
    ++deg[y];
}

void dfs(int x) {
    a.push_back(x);
    siz[x] = vis[x] = 1;
    for (int i = h[x]; i; i = ne[i]) {
        int y = ver[i];
        if (vis[y]) continue;
        dis[y] = dis[x] + 1;
        dfs(y);
        siz[x] += siz[y];
    }
    a.push_back(x);
}

void bfs(int s) {
    queue<int> q;
    q.push(s);
    dis[s] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = h[x]; i; i = ne[i]) {
            int y = ver[i];
            if (dis[y]) continue;
            dis[y] = dis[x] + 1;
            q.push(y);
        }
    }
}

bool topsort(int n) {
    queue<int> q;
    vector<int> ans;
    for (int i = 1; i <= n; ++i) {
        if (deg[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        ans.push_back(x);
        for (int i = h[x]; i; i = ne[i]) {
            int y = ver[i];
            if (--deg[y] == 0) q.push(y);
        }
    }
    return ans.size() == n;
}