第一次BFS尝试,仅仅练习一下:)

#include <iostream>
#include<vector>
#include<list>
#include<queue>
#include<algorithm>
using namespace std;

typedef vector<list<int> > Graph;

void bfs(Graph p)
{
    bool visited[p.size()];
    for(int i=0;i!=(int)p.size();i++)
    {
        visited[i]=false;
    }

queue<int> que;

if(p.empty())
    {
        return;
    }

que.push(0);
    while(!que.empty())
    {
        int visiting_point=que.front();
        que.pop();
        if(!visited[visiting_point])
        {
            cout<<visiting_point<<endl;
            visited[visiting_point]=true;

for(list<int>::iterator iter=p[visiting_point].begin();
            iter!=p[visiting_point].end();iter++)
            {
                que.push(*iter);
            }
        }

}
}

int main()
{
    Graph graph;
    list<int> list0;
    list0.push_back(2);
    list<int> list1;
    list1.push_back(2);
    list<int> list2;
    list2.push_back(0);
    list2.push_back(1);

graph.push_back(list0);
    graph.push_back(list1);
    graph.push_back(list2);

bfs(graph);

return 0;
}

时间: 09-17

第一次BFS尝试,仅仅练习一下:)的相关文章

Codeforces Gym 100187E E. Two Labyrinths bfs

E. Two Labyrinths Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/gym/100187/problem/E Description A labyrinth is the rectangular grid, each of the cells of which is either free or wall, and it's possible to move only between free

windows phone应用开发尝试

这个应用,其实也算不上应用,是自己第一次真正尝试编写的程序,全程用XAML编写,由于之前学C#时过于急功近利,现在C#已经忘光了,废话不多说,下面开始介绍: UI如下: 这个应用其实就是通过HyperlinkButtonl控件来调取一些微软常用应用的网页版,主要控件是Grid.HyerlinkButton还有Flyout,因此,这个应用基本不具有任何实用性,唯一的作用就是练练手.这一应用,有一模块为『尚未开发中....』,点击Setting也会弹出如下信息,显然应用并不完整 没办法,目前能力有限

两个bfs题:逃跑和奇怪的最短路

bfs 搜索状态多加一维表示时间vis[x][y][t]表示t时间能否到达点(x,y)对于每个士兵,预处理出哪些时间哪些点是不可访问 这题看着提示瞎写一通结果过了..恍恍惚惚 #include <cstdio> #include <algorithm> #include <set> #include <map> #include <iostream> #include <string> #include <queue> #

UVa1599 Ideal Path(双向bfs+字典序+非简单图的最短路+队列判重)

题目大意: 对于一个n个房间m条路径的迷宫(Labyrinth)(2<=n<=100000, 1<=m<=200000),每条路径上都涂有颜色,颜色取值范围为1<=c<=10^9.求从节点1到节点n的一条路径,使得经过的边尽量少,在这样的前提下,如果有多条路径边数均为最小,则颜色的字典序最小的路径获胜.一条路径可能连接两个相同的房间,一对房间之间可能有多条路径.输入保证可以从节点1到达节点n. 更多细节可以参考原题:UVa1599 分析: 从题目中我们可以看出,题目中的

有向图最短路 bfs NOIP2014 道路搜索

寻找道路 题目描述 在有向图G 中,每条边的长度均为1 ,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件: 1 .路径上的所有点的出边所指向的点都直接或间接与终点连通. 2 .在满足条件1 的情况下使路径最短. 注意:图G 中可能存在重边和自环,题目保证终点没有出边. 请你输出符合条件的路径的长度. 输入输出格式 输入格式: 输入文件名为road .in. 第一行有两个用一个空格隔开的整数n 和m ,表示图有n 个点和m 条边. 接下来的m 行每行2 个整数x .y ,

NOIP2009 最优贸易(BFS)

本题正解是tarjan,我没有去写 用两次BFS,第一次BFS在原图的反图上做,从n开始,找到从n出发能够达到到达的所有点. 第二次BFS从起点开始,保存每个点到n点路径上面的最小值mp[i]. 最后遍历一遍,求出w[i]-mp[i]的最大值即可. #include<cstdio> #include<iostream> #include<queue> #include<cstring> #define MAXN 100005 using namespace

第一次使用Git心得体会

用书本上的概念讲,Git是一个分布式的版本控制工具,每一个Git的工作目录都是一个完全独立的代码库,并拥有完整的历史记录和版本追踪能力,能够不依赖于网络和中心服务器.也就是说Git能够不需要服务器而在随意的Linux机器上管理代码,其实这也是它的优势所在,我对Git的认识不深,单从课堂上老师的只言片语便可以了解到它的深奥,我的学习之旅也才刚刚开始. 使用Git之后,我才逐步了解到Git的管理是在本地建立储存仓库,换句话说,代码与管理仓库是形影不离的,这种方式可以在某种程度上减轻服务器的负担. 我

hihocoder#1050 : 树中的最长路(树中最长路算法 两次BFS找根节点求最长+BFS标记路径长度+bfs不容易超时,用dfs做TLE了)

#1050 : 树中的最长路 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上回说到,小Ho得到了一棵二叉树玩具,这个玩具是由小球和木棍连接起来的,而在拆拼它的过程中,小Ho发现他不仅仅可以拼凑成一棵二叉树!还可以拼凑成一棵多叉树——好吧,其实就是更为平常的树而已. 但是不管怎么说,小Ho喜爱的玩具又升级换代了,于是他更加爱不释手(其实说起来小球和木棍有什么好玩的是吧= =).小Ho手中的这棵玩具树现在由N个小球和N-1根木棍拼凑而成,这N个小球都被小Ho标上了不

UVA 1599 Ideal Path(双向bfs+字典序+非简单图的最短路+队列判重)

https://vjudge.net/problem/UVA-1599 给一个n个点m条边(2<=n<=100000,1<=m<=200000)的无向图,每条边上都涂有一种颜色.求从结点1到结点n的一条路径,使得经过的边数尽量少,在此前提下,经过边的颜色序列的字典序最小.一对结点可能有多条边,一条边可能连接相同的结点(自环).输入保证结点1可以到达结点n.颜色是1~10^9的整数. 分析: 从题目中我们可以看出,题目中的无向图是可以出现自环和重边的,自环我们可以在输入的时候检查并排