【PTA数据结构 | C语言版】欧拉回路

本专栏持续输出数据结构题目集，欢迎订阅。

题目

本题请你编写程序，输出给定无向连通图中的欧拉回路。

输入格式：
输入首先在第一行给出图中最大顶点数量，即正整数 kMaxVertex（≤20）。
第二行给出两个正整数，依次为当前要创建的图的顶点数 n 和边数 m（保证顶点数至少为 3 且不超过最大顶点数量）。
随后 m 行，每行给出一条无向边的两个端点的编号。顶点编号从 0 开始，编号间以 1 个空格分隔。
题目保证没有边被重复给出，并且图一定是连通的。

输出格式：
如果欧拉回路不存在，在一行中输出 No Euler circuit.。
如果欧拉回路存在，在一行中按以下格式输出：

0->v1->v2->...->0

其中 v1、v2 等为欧拉回路途径的顶点编号。注意回路必须从编号为 0 的顶点开始，并以回到编号为 0 的顶点结束。

输入样例 1：
20
12 21
1 3
1 4
2 3
2 8
3 4
3 6
3 7
3 9
4 5
4 7
4 10
4 11
5 10
6 9
7 9
7 10
8 9
9 0
9 10
10 11
10 0

输出样例 1：
0->10->7->9->8->2->3->4->1->3->9->6->3->7->4->5->10->11->4->10->9->0

注意：欧拉回路的输出顺序是不唯一的，以任何顺序输出都可以，有特殊裁判程序判断输出的正确性。例如下列输出也是正确的。

0->9->10->5->4->3->1->4->7->9->8->2->3->6->9->3->7->10->11->4->10->0

输入样例 2：
20
4 5
0 1
1 2
2 3
3 0
2 0

输出样例 2：
No Euler circuit.

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VERTEX 20

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct {
    Node* adj[MAX_VERTEX];
    int n;
} Graph;

typedef struct {
    int data[MAX_VERTEX * MAX_VERTEX];
    int top;
} Stack;

// 函数声明
void initGraph(Graph* g, int n);
void addEdge(Graph* g, int src, int dest);
int isEulerian(Graph* g);
void findEulerCircuit(Graph* g);
void initStack(Stack* s);
void push(Stack* s, int v);
int pop(Stack* s);
int isEmpty(Stack* s);
int peek(Stack* s);

int main() {
    int kMaxVertex;
    scanf("%d", &kMaxVertex);
    
    int n, m;
    scanf("%d %d", &n, &m);
    
    Graph g;
    initGraph(&g, n);
    
    for (int i = 0; i < m; i++) {
        int src, dest;
        scanf("%d %d", &src, &dest);
        addEdge(&g, src, dest);
    }
    
    if (!isEulerian(&g)) {
        printf("No Euler circuit.\n");
    } else {
        findEulerCircuit(&g);
    }
    
    return 0;
}

// 初始化图
void initGraph(Graph* g, int n) {
    g->n = n;
    for (int i = 0; i < n; i++) {
        g->adj[i] = NULL;
    }
}

// 添加无向边
void addEdge(Graph* g, int src, int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = g->adj[src];
    g->adj[src] = newNode;
    
    newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = src;
    newNode->next = g->adj[dest];
    g->adj[dest] = newNode;
}

// 检查是否所有顶点度数为偶数
int isEulerian(Graph* g) {
    for (int i = 0; i < g->n; i++) {
        int degree = 0;
        Node* temp = g->adj[i];
        while (temp != NULL) {
            degree++;
            temp = temp->next;
        }
        if (degree % 2 != 0) {
            return 0; // 存在奇度顶点，不是欧拉图
        }
    }
    return 1; // 所有顶点度数均为偶数
}

// 初始化栈
void initStack(Stack* s) {
    s->top = -1;
}

// 入栈
void push(Stack* s, int v) {
    s->data[++(s->top)] = v;
}

// 出栈
int pop(Stack* s) {
    return s->data[(s->top)--];
}

// 检查栈是否为空
int isEmpty(Stack* s) {
    return s->top == -1;
}

// 获取栈顶元素
int peek(Stack* s) {
    return s->data[s->top];
}

// 查找并输出欧拉回路
void findEulerCircuit(Graph* g) {
    // 复制邻接表用于删除边
    Node* adjCopy[MAX_VERTEX];
    for (int i = 0; i < g->n; i++) {
        adjCopy[i] = NULL;
        Node* temp = g->adj[i];
        while (temp != NULL) {
            Node* newNode = (Node*)malloc(sizeof(Node));
            newNode->vertex = temp->vertex;
            newNode->next = adjCopy[i];
            adjCopy[i] = newNode;
            temp = temp->next;
        }
    }
    
    Stack stack;
    initStack(&stack);
    Stack circuit;
    initStack(&circuit);
    
    push(&stack, 0); // 从顶点0开始
    
    while (!isEmpty(&stack)) {
        int u = peek(&stack);
        
        if (adjCopy[u] == NULL) {
            // 如果当前顶点没有邻接边，加入回路
            push(&circuit, pop(&stack));
        } else {
            // 否则选择一个邻接顶点，删除边，继续DFS
            int v = adjCopy[u]->vertex;
            push(&stack, v);
            
            // 在u的邻接表中删除v
            Node* temp = adjCopy[u];
            adjCopy[u] = adjCopy[u]->next;
            free(temp);
            
            // 在v的邻接表中删除u
            Node* prev = NULL;
            temp = adjCopy[v];
            while (temp != NULL && temp->vertex != u) {
                prev = temp;
                temp = temp->next;
            }
            if (prev == NULL) {
                adjCopy[v] = temp->next;
            } else {
                prev->next = temp->next;
            }
            free(temp);
        }
    }
    
    // 输出欧拉回路
    int first = 1;
    while (!isEmpty(&circuit)) {
        if (!first) {
            printf("->");
        }
        printf("%d", pop(&circuit));
        first = 0;
    }
    printf("\n");
    
    // 释放复制的邻接表内存
    for (int i = 0; i < g->n; i++) {
        Node* temp = adjCopy[i];
        while (temp != NULL) {
            Node* next = temp->next;
            free(temp);
            temp = next;
        }
    }
}