Preface

学校码图的数据结构实验第三题，~~因为是码图所以可以随便欺负~~;

DFS模板题，熟读教材就能送分;

让我们开始吧！

Content

这里是题目:图的深度优先遍历

分别用邻接矩阵和邻接链表两种数据结构实现图的深度优先遍历算法，输出遍历的结点序列，并分析算法的时间复杂度。

提交格式：邻接矩阵数据结构实现void solveA(int n, int m, int e[][2], int out[])函数。邻接链表数据结构实现void solveB(int n, int m, int e[][2], int out[])函数。参数n为结点个数，m为边条数，e为所有边，out为输出序列。1<=n<=3000,1<=m<=100000,0<=e[i][j]<n。遍历的起始结点为0，邻接矩阵数据结构中按行从左到右遍历邻居结点，邻接链表数据结构中按存储顺序遍历邻居结点，图为无向图。请不要printf输出任何内容。

输入样例： n=5,m=10,e={{2,4},{3,0},{0,2},{3,1},{4,1},{0,1},{3,4},{2,3},{1,2},{0,4}} 输出样例： solveA：out={0,1,2,3,4} solveB：out={0,3,1,4,2}

DFS模板题，就不介绍了; 直接贴代码;

#include <vector>
const int maxn=3005;
int matrix[maxn][maxn];
std::vector<int> adj[maxn];
int visa[maxn];
void dfsA(int n,int now,int&cnta,int out[]){
    visa[now]=1;
    out[cnta++]=now;
    for(int j=0;j<n;j++){
        if(matrix[now][j]==1&&!visa[j]){
            dfsA(n,j,cnta,out);
        }
    }
    return ;
}
void solveA(int n,int m,int e[][2],int out[]){
    for(int i=0;i<m;i++){
        matrix[e[i][0]][e[i][1]]=1;
        matrix[e[i][1]][e[i][0]]=1;
    }
    int cnta=0;
    dfsA(n,0,cnta,out);
    return ;
}

int visb[maxn];
void dfsB(int n,int now,int&cntb,int out[]){
    visb[now]=1;
    out[cntb++]=now;
    for(int i=0;i<adj[now].size(); i++){
        if( !visb[adj[now][i]]){
            dfsB(n,adj[now][i],cntb,out);
        }
    }
    return ;
}
void solveB(int n,int m,int e[][2],int out[]){
    for(int i=0;i<m;i++){
        adj[e[i][1]].push_back(e[i][0]);
        adj[e[i][0]].push_back(e[i][1]); 
    }
    int cntb=0;
    dfsB(n,0,cntb,out);
}