用C语言编程：判断一个有向图是否连通图，如若是，再判断其是否是欧拉图

好的，这是一个经典的图论问题。我们可以使用深度优先搜索（DFS）来判断有向图是否连通，同时使用欧拉回路的判定条件来判断是否为欧拉图。

以下是使用C语言的代码实现：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

// 邻接表存储图
typedef struct ArcNode {
    int adjvex; // 该弧所指向的顶点的位置
    struct ArcNode *nextarc; // 指向下一条弧的指针
} ArcNode;

typedef struct VNode {
    int data; // 顶点信息
    ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices; // 图中顶点的数组
    int vexnum, arcnum; // 顶点数和弧数
} ALGraph;

// 创建有向图
void createGraph(ALGraph *G) {
    printf("请输入有向图的顶点数和弧数（以空格分隔）：\n");
    scanf("%d%d", &(G->vexnum), &(G->arcnum));

    // 初始化每个顶点
    for (int i = 0; i < G->vexnum; i++) {
        printf("请输入第%d个顶点的值：\n", i + 1);
        scanf("%d", &(G->vertices[i].data));
        G->vertices[i].firstarc = NULL;
    }

    // 添加每条弧
    printf("请输入每条弧的起点和终点（以空格分隔）：\n");
    for (int i = 0; i < G->arcnum; i++) {
        int s, t;
        scanf("%d%d", &s, &t);

        // 添加弧<s, t>
        ArcNode *p = (ArcNode*) malloc(sizeof(ArcNode));
        p->adjvex = t - 1;
        p->nextarc = G->vertices[s - 1].firstarc;
        G->vertices[s - 1].firstarc = p;
    }
}

// DFS遍历有向图
void DFS(ALGraph *G, int v, bool *visited) {
    visited[v] = true; // 标记当前顶点为已访问

    // 遍历该顶点的所有出边
    for (ArcNode *p = G->vertices[v].firstarc; p; p = p->nextarc) {
        int w = p->adjvex; // 获取该出边指向的顶点

        if (!visited[w]) { // 如果该顶点未被访问过，则递归遍历
            DFS(G, w, visited);
        }
    }
}

// 判断有向图是否为连通图
bool isConnected(ALGraph *G) {
    bool visited[MAX_VERTEX_NUM] = { false };

    DFS(G, 0, visited); // 从第一个顶点开始遍历

    // 如果有任意一个顶点未被访问，则说明该图不是连通图
    for (int i = 0; i < G->vexnum; i++) {
        if (!visited[i]) {
            return false;
        }
    }

    return true;
}

// 获取顶点的入度
int getInDegree(ALGraph *G, int v) {
    int count = 0;

    for (int i = 0; i < G->vexnum; i++) {
        for (ArcNode *p = G->vertices[i].firstarc; p; p = p->nextarc) {
            if (p->adjvex == v) {
                count++;
            }
        }
    }

    return count;
}

// 获取顶点的出度
int getOutDegree(ALGraph *G, int v) {
    int count = 0;

    for (ArcNode *p = G->vertices[v].firstarc; p; p = p->nextarc) {
        count++;
    }

    return count;
}

// 判断有向图是否为欧拉图
bool isEulerian(ALGraph *G) {
    if (!isConnected(G)) { // 如果不是连通图，则一定不是欧拉图
        return false;
    }

    // 统计每个顶点的入度和出度
    int inDegree[MAX_VERTEX_NUM] = { 0 };
    int outDegree[MAX_VERTEX_NUM] = { 0 };
    for (int i = 0; i < G->vexnum; i++) {
        inDegree[i] = getInDegree(G, i);
        outDegree[i] = getOutDegree(G, i);
    }

    int startVertex = 0, endVertex = 0; // 记录起点和终点的个数

    // 如果每个顶点的入度和出度都相等，则是欧拉回路
    // 如果只有一个顶点的出度比入度大1，只有一个顶点的入度比出度大1，则是欧拉通路
    // 其余情况均不是欧拉图
    for (int i = 0; i < G->vexnum; i++) {
        if (inDegree[i] != outDegree[i]) {
            if (inDegree[i] - outDegree[i] == 1) {
                endVertex++;
            } else if (outDegree[i] - inDegree[i] == 1) {
                startVertex++;
            } else {
                return false;
            }
        }
    }

    if (startVertex == 1 && endVertex == 1) {
        return true;
    }

    if (startVertex == 0 && endVertex == 0) {
        return true;
    }

    return false;
}

int main() {
    ALGraph G;

    createGraph(&G);

    if (isConnected(&G)) {
        printf("该有向图是连通图！\n");

        if (isEulerian(&G)) {
            printf("该有向图是欧拉图！\n");
        } else {
            printf("该有向图不是欧拉图！\n");
        }
    } else {
        printf("该有向图不是连通图！\n");
    }

    return 0;
}

代码中使用了邻接表存储图，使用深度优先搜索（DFS）遍历图，并使用入度和出度的统计来判断是否为欧拉图。