您现在的位置是：首页 >其他 >review 并查集+DFS+BFS网站首页其他

并查集：

查找：

int p[N];//定义多个集合

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    /*
    经上述可以发现,每个集合中只有祖宗节点的p[x]值等于他自己,即:
    p[x]=x;
    */
    return p[x];
    //找到了便返回祖宗节点的值
}

合并：

p[find(a)] = find(b);

DFS+BFS：

DFS:

DFS没有模板，最重要的是搜索顺序。用什么顺序遍历所有方案

void dfs(当前状态)
{
    if(当前状态是目标状态) //判断
       进行相应处理(输出当前解、更新最优解、退出返回等)
    // 扩展
    for(所有可行的新状态)
    {
        if(新状态没有访问过 && 需要访问) //可行性剪枝、最优性剪枝、重复性剪枝
        {
            标记
            dfs(新状态);
            取消标记
            恢复现场
        }
    }
}

BFS:

搜索顺序是一层一层的，一般的搜索问题要求输出最优解先考虑BFS,一层一层搜只要搜到就结束，搜到的一定是最优的。

// 判重数组st[]
//设置偏移量
queue定义队列并初始化
while(queue 非空)
{
    t取队头元素
    for(拓展 t )
    {
        int x,y;//(新节点)+用偏移量
        if(!st[])
        {
            //将新节点入队
        }
    }
}