05-图1. List Components (25)

Posted on   |   In   |  

For a given undirected graph with N vertices and E edges, please list all the connected components by both DFS and BFS. Assume that all the vertices are numbered from 0 to N-1. While searching, assume that we always start from the vertex with the smallest index, and visit its adjacent vertices in ascending order of their indices.

Input Specification:

Each input file contains one test case. For each case, the first line gives two integers N (0<N<=10) and E, which are the number of vertices and the number of edges, respectively. Then E lines follow, each described an edge by giving the two ends. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in each line a connected component in the format “{ v1 v2 … vk }”. First print the result obtained by DFS, then by BFS.

Sample Input:

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

Sample Output:

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

代码如下：

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
100
101
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Graph
{
public:
    Graph(int vertexNum, int edgeNum):vertexNum(vertexNum), edgeNum(edgeNum)
    {
        m_graph.resize(vertexNum);
        visited.resize(vertexNum, 0);
        int startVertex = 0, endVertex = 0;
        for(int i = 0; i < edgeNum; ++i)        //save graph
        {
            cin >> startVertex >> endVertex;
            m_graph[startVertex].push_back(endVertex);
            m_graph[endVertex].push_back(startVertex);
        }
        for(int i = 0; i < vertexNum; ++i)      //sort it in order to visit its adjacent vertices in ascending order of their indices
        {
            sort(m_graph[i].begin(), m_graph[i].end(), less<int>());
        }
    };
    void BFS(int index);
    void DFS(int index);
    void Travalsal(bool flag);
private:
    int vertexNum;
    int edgeNum;
    vector<int> visited;
    vector<vector<int> > m_graph;
};

void Graph::Travalsal(bool flag)
{
    for(int i = 0; i < vertexNum; ++i)
    {
        if(!visited[i])
        {
            cout << "{" << " ";
            if(flag)
            {
                DFS(i);
            }
            else
            {
                BFS(i);
            }
            cout << "}" << endl;
        }
    }
    for(int i = 0; i < visited.size(); ++i)
    {
        visited[i] = 0;
    }
}

void Graph::BFS(int index)
{
    int queueGraph[46];
    int rear = -1, front = -1;
    queueGraph[++front] = index;
    while(rear != front)
    {
        int num = queueGraph[++rear];
        if(!visited[num])
        {
            cout << num << " ";
            visited[num] = 1;
            for(int i = 0; i < m_graph[num].size(); ++i)
            {
                queueGraph[++front] = m_graph[num][i];
            }
        }
    }
}

void Graph::DFS(int index)
{
    if(!visited[index])
    {
        visited[index] = 1;
        cout << index << " ";
        for(int i = 0; i < m_graph[index].size(); ++i)
        {
            DFS(m_graph[index][i]);
        }
    }

}

int main()
{
    int N = 0, M = 0;
    cin >> N >> M;
    Graph graph(N, M);
    graph.Travalsal(true);
    graph.Travalsal(false);
    return 0;
}

本题比较简单，测试结果如下：

测试点 结果 用时(ms) 内存(kB) 得分/满分
0 答案正确 1 308 15/15
1 答案正确 1 184 8/8
2 答案正确 1 308 2/2