大四的萌新辣！

列出联通集

Posted on Edited on In Valine:

问题描述

给一个无向图 N个顶点（0 ~ N-1） E条边 从第0个顶点开始DFS/BFS遍历这个无向图

按照编号递增的顺序访问邻接点.

题目链接:

https://pintia.cn/problem-sets/15/problems/714

数据范围:

0 <= N <= 10

E未知

样例:

Input:

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

Output:

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

知识点

无（基础BFS/DFS）

题目做法

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
#define debug {printf("AC!!!\n");}
using namespace std;
const int maxn = 10 + 5;
int G[maxn][maxn];//无向图
int vis[maxn];//标记该点是否访问过
int N, E;
void DFS(int x)
{
    vis[x] = 1;
    cout << x << " ";
    for(int i1 = 0; i1 < N; i1++)
    {
        if(!vis[i1] && G[x][i1])
            DFS(i1);
    }
}
void BFS(int x)
{

    queue<int> q;
    q.push(x);
    vis[x] = 1;//
    while(!q.empty())
    {
        //debug
        int flag = q.front();
        cout << flag << " ";
        q.pop();
        for(int i1 = 0; i1 < N; i1++)
        {
            if(!vis[i1] && G[flag][i1])
            {
                vis[i1] = 1;
                q.push(i1);
            }
        }
    }
}
int main(void)
{
    cin >> N >> E;
    memset(G, 0, sizeof(G));
    memset(vis,0, sizeof(vis));
    for(int i = 0; i < E; i++)
    {
        int a, b;
        cin >> a >> b;
        G[a][b] = 1;
        G[b][a] = 1;
        //无向图建图细节
    }
    memset(vis, 0, sizeof(vis));
    //DFS
    for(int i = 0; i < N; i++)
    {
        if(!vis[i])//标记访问
        {
            //cout <<"第" << i <<"个点的DFS搜索:" << endl;
            cout << "{ ";
            DFS(i);
            cout << "}" << endl;
        }
    }

    //BFS
    memset(vis, 0, sizeof(vis));

    for(int i = 0; i < N; i++)
    {
        //debug
        if(!vis[i])//标记访问
        {
            //cout <<"第" << i <<"个点的BFS搜索:" << endl;
            cout << "{ ";
            BFS(i);
            cout << "}" << endl;
        }
    }
    return  0;
}
/*
input:
8 6
0 7
0 1
2 0
4 1
2 4
3 5

output:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }
*/

总结点

  1. 第一次提交的时候，获得了WA。

    然后输出各个环节的程序，发现在queue处并没有进行执行。

    ……

    发现没有添加

    1
    memset(vis, 0, sizeof(vis));

    这一行代码。。。。。。

    菜死了….BFS递归遍历完后要清空标记数组再DFS。。。。。。

    找了好久…

  2. 输出样例细节点：注意空格的位置及其按序号排列的遍历顺序换行。

  3. BFS写的不多 要多加练习。

参考资料

kuangbin搜索专题：https://vjudge.net/article/720