Title Description

Description realize the adjacency table storage structure of the graph and some basic operation functions. On this basis, the depth traversal algorithm of graph is realized and tested. This question only gives part of the code, please complete the content. Input format
First line: enter an integer between 0 and 3 (directed graph: 0, directed net: 1, undirected graph: 2, undirected net: 3);
The second line: enter the number of vertices and edges;
The third line: enter the value of each vertex (character type, length ＜ 3); (traversal starts from the first vertex of input)
The fourth line: input the arc tail and arc head of each arc (edge) (with space as the interval), and input the weight if it is a net;

Output format
Output the result of traversing the depth of the graph.

sample input
0
3 3
a b c
a b
b c
c b

sample output
a b c

Problem solving ideas

Before deep search, the map needs to be built. Here, the variable array (vector) is used to simulate the linked list to build the map
N < = 1 is a directed graph, which needs an assignment
n> 1 is an undirected graph, which requires two assignments.
Then there is a basic deep search template

AC code (DFS)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int M=1e5+5;
vector <int> e[M];
int book[M];
void dfs(int cur)
{
    cout<<(char)(cur+'a')<<' ';
    int len=e[cur].size();
    for(int i=0;i<len;i++)
    {
        int y=e[cur][i];
        if(book[y]==0)
        {
            book[y]=1;
            dfs(y);
        }
    }
    return ;
}

int main()
{
    ios::sync_with_stdio(false);
    int t;cin>>t;
    int n,m;cin>>n>>m;
    int st;
    for(int i=0;i<n;i++)
    {
        char x;cin>>x;/*cjb*/
    }
    for(int i=0;i<m;i++)
    {
        char x,y;cin>>x>>y;
        int a=(char)(x-'a');
        int b=(char)(y-'a');
        if(i==0)
        {
            st=a;
        }
        if(t<=1)
        {
            e[a].push_back(b);
        }
        else
        {
            e[a].push_back(b);
            e[b].push_back(a);
        }
    }
    book[st]=1;
    dfs(st);
    return 0;
}


8649 Breadth traversal of Graphs

Title Description

Description
The storage structure and basic operation function of adjacency table are realized by using the depth traversal of graph. On this basis, the breadth traversal algorithm of graph is realized and tested. Pay attention to the correct use of queue storage structure.

Input format
First line: enter an integer between 0 and 3 (directed graph: 0, directed net: 1, undirected graph: 2, undirected net: 3);
The second line: enter the number of vertices and edges;
The third line: enter the value of each vertex (character type, length ＜ 3); (traversal starts from the first vertex of input)
The fourth line: input the arc tail and arc head of each arc (edge) (with space as the interval), and input the weight if it is a net;

Output format
Output the result of traversing the breadth of the graph

sample input
0
3 3
a b c
a b
b c
c b

sample output
a b c

Tips

Author yqm

Problem solving ideas

The main problem is the storage of the map. After it is stored, it can be set directly into the BFS

AC code (BFS)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int M=1e5+5;
vector <int> e[M];
int q[M];
int book[M];
int main()
{
    ios::sync_with_stdio(false);
    int t;cin>>t;
    int n,m;cin>>n>>m;
    int st;
    for(int i=0;i<n;i++)
    {
        char x;cin>>x;/*cjb*/
    }
    for(int i=0;i<m;i++)
    {
        char x,y;cin>>x>>y;
        int a=(char)(x-'a');
        int b=(char)(y-'a');
        if(i==0)
        {
            st=a;
        }
        if(t<=1)
        {
            e[a].push_back(b);
        }
        else
        {
            e[a].push_back(b);
            e[b].push_back(a);
        }
    }
    int head=0,tail=0;
    book[st]=1;
    q[tail++]=st;
    while(head<tail)
    {
        int y=q[head];
        head++;
        int len=e[y].size();
        cout<<(char)(y+'a')<<' ';
        for(int i=0;i<len;i++)
        {
            if(book[e[y][i]]==0)
            {
                book[e[y][i]]=1;
                q[tail++]=e[y][i];
            }
        }
    }
    return 0;
}