基于邻接表的广度优先搜索遍历

~题目链接~

http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2142&cid=1186

输入

1
6 7 0
0 3
0 4
1 4
1 5
2 3
2 4
3 5

输出

0 3 4 2 5 1

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<vector>
#define maxn 100

using namespace std;

vector<int>list[100];//STL，定义一个二维动态数组,每一行是用一个vector储存这一行的数据。
int visited[100],q,flag,i;

void BFS(int t)
{
    queue<int>Q;//STL，队列
    Q.push(t);
    visited[t]=1;
    while(!Q.empty())
    {
        q=Q.front();
        Q.pop();
        if(!flag)
        {
            printf("%d",q);
            flag=1;
        }
        else
            printf(" %d",q);
        for(i=0; i<list[q].size(); i++)//v.size() 表示vector中存入元素的个数
        {
            if(!visited[list[q][i]])
            {
                Q.push(list[q][i]);
                visited[list[q][i]]=1;
            }
        }

    }
}

int main()
{
    int n,k,m,t,u,v;
    scanf("%d",&n);
    while(n--)
    {
        flag=0;
        memset(visited,0,sizeof(visited));
        scanf("%d%d%d",&k,&m,&t);
        for(i=0; i<m; i++)
        {
            scanf("%d%d",&u,&v);
            list[u].push_back(v);
            list[v].push_back(u);
        }
        BFS(t);
    }

    return 0;
}