输入格式
输入的第一行为两个整数 nn 和 mm(1 < n \leq 1001<n≤100,1 \leq m \leq 2001≤m≤200),代表图中的顶点数和边数。接下来的 mm 行,每行输入两个整数 xx(0 \leq x \leq n-10≤x≤n−1) 和 yy(0 \leq y \leq n-10≤y≤n−1),表示一条从 xx 连向 yy 的无向边。之后输入一个整数 kk(0 \leq k < n0≤k<n),表示深度优先搜索的起点。
输出格式
输出深度优先搜索的遍历结果,每个元素各占一行。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 10000
typedef struct Node {
int vertex;
struct Node *next;
} Node, *LinkedList;
LinkedList insert_node(LinkedList head, int index) {
Node *node = (Node *)malloc(sizeof(Node));
node->vertex = index;
node->next = head;
head = node;
return head;
}
typedef struct Graph {
LinkedList edges[MAX_N];
int n;
int visited[MAX_N];
} Graph;
void init(Graph * g, int n) {
g->n = n;
for (int i = 0; i < g->n; ++i) {
g->edges[i] = NULL;
}
memset(g->visited,0,sizeof(g->visited));
}
void insert(Graph *g, int x, int y) {
if (x < 0 || x >= g->n || y < 0 || y >= g->n) {
return ;
}
g->edges[x] = insert_node(g->edges[x], y);
g->edges[y] = insert_node(g->edges[y], x);
}
void clear(Graph *g) {
for (int i = 0; i < g->n; ++i) {
Node *head = g->edges[i];
while (head != NULL) {
Node *delete_node = head;
head = head->next;
free(delete_node);
}
}
free(g);
}
void dfs(Graph *g, int index) {
printf("%d\n",index);
g->visited[index]=1;
for(Node *adj=g->edges[index];adj!=NULL;adj=adj->next)
{
if(g->visited[adj->vertex]!=1)
{
dfs(g,adj->vertex);
}
}
}
int main() {
int n, m, k;
scanf("%d %d", &n, &m);
Graph *graph = (Graph *)malloc(sizeof(Graph));
init(graph, n);
for (int i = 0; i < m; ++i) {
int x, y;
scanf("%d %d", &x, &y);
insert(graph, x, y);
}
scanf("%d", &k);
dfs(graph, k);
clear(graph);
return 0;
}