搜索模板

dfs模板

void dfs(int x)
{
    v[x] = 1; // 记录点x被访问过，v是visit的缩写
    for (int i = h[x]; ~i; i = ne[i])
    {
        int y = e[i];
        if (v[y]) continue; // 点y已经被访问过了
        dfs(y);
    }
}

树的dfs序

void dfs(int x)
{
    a[ ++ m] = x; // a数组存储dfs序
    v[x] = 1; // 记录点x被访问过
    for (int i = h[x]; ~i; i = ne[i])
    {
        int y = e[i];
        if (v[y]) continue;
        dfs(y);
    }
    a[ ++ m] = x;
}

树的深度

void dfs(int x)
{
    v[x] = 1;
    for (int i = h[x]; ~i; i = ne[i])
    {
        int y = e[i];
        if (v[y]) continue;
        d[y] = d[x] + 1; // 从父节点到子节点y递推, 计算深度
        dfs(y);
    }
}

树的重心

void dfs(int x)
{
    v[x] = 1;
    size[x] = 1; // 子树x的大小
    int max_part = 0; // 删掉x后分成的最大子树的大小
    for (int i = h[x]; ~i; i = ne[i])
    {
        int y = e[i];
        if (v[y]) continue; // 点y已经被访问过了
        dfs(y);
        size[x] += size[y]; // 从子节点向父节点递推
        max_part = max(max_part, size[y]); 
    }
    max_part = max(max_part, n - size[x]); // n为整棵树的节点数目
    if (max_part < ans)
    {
        ans = max_part; // 全局变量ans记录重心对应的max_part值
        pos = x; // 全局变量pos记录了重心
    }
}

图的连通块划分

cnt是无向图包含的连通块的个数, v数组标记了每个点属于哪一个连通块.

void dfs(int x)
{
    v[x] = cnt;
    for (int i = h[x]; ~i; i = ne[i])
    {
        int y = e[i];
        if (v[y]) continue;
        dfs(y);
    }
}

for (int i = 1; i <= n; i ++ ) // 在int main()中
    if (!v[i])
    {
        cnt ++ ;
        dfs(i);
    }

bfs模板

y总一般是数组模拟queue,这里放一个STL的.

void bfs()
{
    memset(d, 0, sizeof d);
    queue<int> q;
    q.push(1);
    d[1] = 1;
    while (q.size() > 0)
    {
        int x = q.front();
        q.pop();
        for (int i = h[x]; ~i; i = ne[i])
        {
            int y = e[i];
            if (d[y]) continue;
            d[y] = d[x] + 1;
            q.push(y);
        }
    }
}

对于一棵树来说，d[x] 就是点 x 在树中的深度。对于一张图来说,d[x] 被称为点 x 的层次(从起点 1 走到点 x 需要经过的最少点数)。
它具有两个重要性质：
(1)在访问完所有的第 i 层节点后, 才会开始访问第 i + 1 层节点.
(2)任意时刻, 队列中至多有两个层次的节点.其中一部分节点属于第 i 层,则另一部分节点属于第 i + 1 层,并且所有第 i 层节点排在第 i + 1 层节点之前.也就是说,广度优先遍历队列中的元素关于层次满足”两段性”和”单调性”.